看到题目，首先想到的是两个for

这样可以遍历所有的情况，但是会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        area = 0
        i = 0
        j = len(height) - 1
        for i in range(j): # 从左边开始遍历左边的高
            for j in range(j, i, -1): # 从右边开始遍历右边的高
            		# 最矮的作为高，计算面积
                realheight = min(height[i], height[j])
                realarea = realheight * (j - i)
                area = max(area, realarea)


                if height[i] < height[j]:
                    break
        return area

那么这个时候可以利用双指针，每次只移动最小的那个边，减少遍历的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        right = len(height) - 1
        left = 0
        area = 0
        
        while left < right:
            realarea = min(height[left], height[right]) * (right - left)
            area = max(area, realarea)

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
            
        return area