盛最多水的容器

0x1 题目详情

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2

测试用例: 输入：[1,8,6,2,5,4,8,3,7] 输出：49

0x2 思路

当我在看到这道题时，我一直在思考如何使用单调栈求解，但是无论是单调递增栈还是单调递减栈都不能很好的解决题目，最后迫不得已看了答案，发现竟然如此简单，何况这道题还是二刷，惭愧啊!

使用双指针我是没想到的，

双指针的思路很简单：使用left和right两个指针指向数组的头和尾，当前left和right能够构成的最大水容量为min(height[left],height[right])*width=1x8=8,然后就是重点辣：

可以发现如果移动长度较高的指针即right，那么无论移动到哪，left和right能够构成的面积总由left的高度即1决定，且必定比最初的面积8小。

也就是木桶理论？最大面积由最小值决定。

所以已left=1为左边界装水的最大容量最大值为8，比8大的面积只可能在移动指针left后可能出现。即不断的移动height[left]、height[right]二者之中较小的值，直到left与right相遇。

0x3 代码

因为只需要遍历数组一遍就能获得结果，所以复杂度为$O(N)$

class Solution {
    public int maxArea(int[] height) {
        if(height== null || height.length==0){
            return 0;
        }
        int left=0;
        int right=height.length-1;
        int result=0;
        while(left<right){
            //每轮都会更新最大的面积
            result=Math.max(result,Math.min(height[left],height[right])*(right-left));
            //移动二者高度较小的指针
            if(height[left]<height[right]){
                left++;
            }
            else{
                right--;
            }
        }
        return result;
    }
}

0x4 总结

怎么说呢，这道题我一开始也没想到是双指针，感觉要求数组中某一区域的最值，多指针也可以作为一种思路。