LeetCode热题Hot100 - 盛水最多的容器

一刷~

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

 自己的思路：

用一个字典保存height中每个元素的下标，然后对height从小到大排序，遍历height数组，对每个height[i]，得到原下标pos，计算pos与最左（height[0]）、最右（height[-1]）之间的面积，取最大值。然后超时了。。

class Solution:
    def maxArea(self, height) -> int:
        res = 0
        #使用字典保存每个数字的下标位置
        dic = {}
        for i in range(len(height)):
            if height[i] not in dic:
                dic[height[i]] = [i]
            else:
                dic[height[i]].append(i)
                
        idx = [i for i in range(len(height))]
        height.sort()
        
        #从小到大遍历
        for h in height:
            pos = dic[h].pop()
            res = max(res, (pos-idx[0])*h, (idx[-1]-pos)*h)
            idx.remove(pos)
        
        return res

然后去看了题解，秒啊~

用两个指针，从左右两侧向中间遍历数组，每次向内移动height较小的那个指针（移动较小的指针，则面积可能变大，但移动较大的指针，面积必然变小）。

class Solution:
    def maxArea(self, height) -> int:
        res = 0
        
        left, right = 0, len(height)-1
        while left < right:
            res = max(res, min(height[left], height[right])*(right-left))
            if height[left]<height[right]:
                left+=1
            else:
                right-=1
        return res