题目描述

给定n个非负整数a1,a2,…,an，其中每个代表一个点坐标（i,ai）。

n个垂直线段例如线段的两个端点在（i,ai）和（i,0）。

找到两个线段，与x轴形成一个容器，使其包含最多的水。

备注：你不必倾倒容器。

我的解法——排序+遍历

先将数组数元素的据结构变成[height[i],i]，记录下每个隔断的高度y和原始x坐标位置
再按height[i]将元素排序，从后往前遍历一遍
nlogn的复杂度。
小坑：least和largest初值的设置
结果：beat 4.8%

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        length = len(height)
        for i in range(length):
            height[i] = [height[i],i]
        height.sort(key = lambda x:x[0])
        largest = -1
        least = length
        res = 0
        for i in range(length - 1,-1,-1):
            if(height[i][1] > largest):
                largest = height[i][1]
            if(height[i][1] < least):  # 小坑：由于least和largest初值的设置，这里不能用elif
                least = height[i][1]
            if(abs(largest - height[i][1]) * height[i][0] > res):
                res = abs(largest - height[i][1]) * height[i][0]
            if(abs(least - height[i][1]) * height[i][0] > res):
                res = abs(least - height[i][1]) * height[i][0]
        return res
    

最优解法——双指针

**最优解法 **
用两个指针从两端开始向中间靠拢，如果左端线段短于或等于右端，那么左端右移，反之右端左移，直到左右两端移到中间重合，记录这个过程中每一次组成木桶的容积，返回其中最大的。
因为当左端线段L小于右端线段R时，我们把L右移，这时舍弃的是L与右端其他线段（R-1, R-2, …）组成的木桶，这些木桶是没必要判断的，因为这些木桶的容积肯定都没有L和R组成的木桶容积大。
严谨的证明（反证法）：
- 假设：该算法并没有遍历到容量最大的情况
- 我们令容量最大时的指针为p_left和p_right。根据题设，我们可以假设遍历时左指针先到达p_left，但是当左指针为p_left时，右指针还没有经过p_right左指针就移动了
- 已知当左指针停留在p_left时，它只有在两种场景下会发生改变
  1. 左指针和右指针在p_left相遇，则右指针一定在前往p_left的途中经过p_right，与题设矛盾
  2. 右指针位于p_right右侧且当前的值大于左指针。则在这种情况下，此时容器的盛水量比题设中最大的盛水量还要大，与题设矛盾因此该算法的遍历一定经过了最大的盛水量的情况
n的时间。

public class Solution {
    public int maxArea(int[] height) {
        int maxarea = 0, l = 0, r = height.length - 1;
        while (l < r) {
            maxarea = Math.max(maxarea, Math.min(height[l], height[r]) * (r - l));
            if (height[l] < height[r])
                l++;
            else
                r--;
        }
        return maxarea;
    }
}

参考答案

https://leetcode.com/problems/container-with-most-water/solution/