暴力搜索版本，超时



In [7]:

    
class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        max_area = 0
        for m, a_m in enumerate(height):
            for n, a_n in enumerate(height):
                if n==m: continue
                temp = abs(m-n)*min(a_m, a_n)
                if temp>max_area:
                    max_area = temp
        return max_area



In [8]:

    
s = Solution()



In [9]:

    
s.maxArea([1,1])









    Out[9]:





1



In [ ]:



In [10]:

    
import json



In [116]:

    
f= open("demo.json", "r")
demo_input = json.loads(f.read())



In [117]:

    
demo_input[:5],len(demo_input)









    Out[117]:





([1, 2, 3, 4, 5], 15000)



In [13]:

    
s.maxArea([1,2]),s.maxArea([2,2,2]),









    Out[13]:





(1, 4)



In [14]:

    
%time s.maxArea([1,2])









    



CPU times: user 9 µs, sys: 1 µs, total: 10 µs
Wall time: 13.1 µs






    Out[14]:





1



In [15]:

    
%time s.maxArea(demo_input)









    



CPU times: user 6.66 s, sys: 7.59 ms, total: 6.66 s
Wall time: 6.68 s






    Out[15]:





4913370

剪枝1



In [46]:

    
class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        max_area = 0
        
        for m, a_m in enumerate(height):
            for n in range(m+1, len(height)):
                a_n = height[n]
                temp = abs(m-n)*min(a_m, a_n)
                if temp>max_area:
                    max_area = temp
        return max_area



In [47]:

    
s = Solution()



In [48]:

    
%time s.maxArea(demo_input)









    



CPU times: user 3.22 s, sys: 3.48 ms, total: 3.22 s
Wall time: 3.22 s






    Out[48]:





4913370

剪枝2

新思路

应该怎么办

花了半个小时思考下能否使用动态规划的方法来解决这道题目，发现无法证明

所有转向了剪枝

问题变为了 max(abs(m-n)*min(a[m],a[n]))

一个数组二维搜索问题，最直观的方式当时是通过矩阵搜索剪枝来完成这个任务

矩阵的每一个元素表示以行和列做下标的两条线所能承受的最大水量



In [162]:

    
class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        max_area = 0
        # 初始化矩阵
        x = 0
        y = len(height)-1
        ret = []
        cal =0
        while x!=y:
            if height[x]>height[y]:
                ret.append(abs(y-x)*height[y])
                y-=1
            elif height[x]<=height[y]:
                ret.append(abs(y-x)*height[x])
                x+=1
            cal+=1
        print cal
        max_area = max(ret)
        return max_area



In [163]:

    
s = Solution()



In [164]:

    
%time s.maxArea(demo_input)









    



14999
CPU times: user 6.25 ms, sys: 933 µs, total: 7.18 ms
Wall time: 6.37 ms






    Out[164]:





56250000



In [148]:

    
s.maxArea([1,2]),









    



1






    Out[148]:





(1,)



In [142]:

    
s.maxArea([2,1])









    Out[142]:





1



In [135]:

    
s.maxArea([2,2,2])









    Out[135]:





4

疑问，类似的思路，为什么会超时



In [200]:

    
def test4(m=10000):
    for i in iter(range(m)):
        for j in iter(range(m)): break



In [201]:

    
def test1(m=10000):
    for i in range(m):
        for j in range(m): break        
def test3(m=10000):
    i=j=0
    while i<m:
        i+=1
        j=0
        while j<m: 
            j+=1
            break 
def test2(m=10000):
    for i in range(m):
        break



In [202]:

    
%time test2()
%time test3()
%time test1()
%time test4()









    



CPU times: user 267 µs, sys: 3 µs, total: 270 µs
Wall time: 271 µs
CPU times: user 1.44 ms, sys: 345 µs, total: 1.78 ms
Wall time: 1.51 ms
CPU times: user 1.18 s, sys: 5.82 ms, total: 1.19 s
Wall time: 1.21 s
CPU times: user 1.2 s, sys: 8.05 ms, total: 1.2 s
Wall time: 1.21 s

通过以上例子说明一个问题，python range的方式来进行两重迭代是要动态生成 list的

所以下面的代码虽然和正确代码表达的是一个疑似，但是执行效率完全不是一个数量级



In [160]:

    
class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        max_area = 0
        # 初始化矩阵
        len_h = len(height)
        len_v = len(height)

        ret = []
        cal = 0
        for m in range(0, len_h):
            for n in range(len_v-1, m,-1):
                cal+=1
                if height[m]>=height[n]:
                    len_v-=1
                    ret.append((n-m)*height[n])
                elif height[m]<height[n]:
                    ret.append((n-m)*height[m])
                    break
        max_area = max(ret)
        print len(ret), cal
        return max_area



In [183]:

    
s = Solution()
%time s.maxArea(demo_input)









    



14999 14999
CPU times: user 7.48 ms, sys: 980 µs, total: 8.46 ms
Wall time: 7.62 ms






    Out[183]:





56250000



In [ ]: