LeetCode - 11 - Container With Most Water

题目

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

 

解法

一、暴力破解

暴力破解是妥妥超时。

计算每一个水容器的体积，选出最大值。

    public int maxArea2(int[] height) {
        int maxArea = 0;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                int maxHeight = height[i] < height[j] ? height[i] : height[j];
                int curArea = maxHeight * (j - i);
                if (curArea > maxArea) maxArea = curArea;
            }
        }
        return maxArea;
    }

暴力破解，时间复杂度O(n²)，运行时间约为 TLE。

 

二、双指针（Best Solution）

左指针指向头，右指针指向尾 。首先计算出当前水容器体积，与之前最大水容器体积比较，若大于，更新最大水容器体积。之后指针移动：

• 左指针对应的高度 >= 右指针对应的高度，此时右指针左移
• 左指针对应的高度 < 右指针对应的高度，此时左指针右移

原因是，最大水容器的体积，在左右指针向中间移动的过程中，取决于左右指针中最小的值。所以移左右指针之中较小的值有助于提升水容器的体积。

证明：假设有个没有遍历到的最大水容器，其坐标为 maxLeft 和 maxRight。由于是对 height 数组遍历，那么我们肯定能遍历到 left 或者 right 之一。不妨假设现在遍历到 maxLeft 停下，此时还没有遍历到 maxRight，继续遍历有如下两种情况：

• maxLeft 之后不向右遍历，直到 right 向左遍历结束。此时肯定遍历过 maxRight， 矛盾。
• 到达maxLeft 之后还需要向右遍历。在该程序中，这种情况只可能在 right > left 产生，然而这说明了存在一个更大的水容器，与假设矛盾。

两者都矛盾，故原最大水容器就是最大水容器。

具体可以参考 Leetcode 官方题解和证明。

    public int maxArea(int[] height) {
        int start = 0, end = height.length - 1, maxArea = 0;

        while (start < end) {
            int bottom = end - start, minHeight;
            if (height[start] <= height[end]) {
                minHeight = height[start];
                start++;
            } else {
                minHeight = height[end];
                end--;
            }
            int curArea = bottom * minHeight;
            if (curArea > maxArea) maxArea = curArea;
        }
        
        return maxArea;
    }

双指针，时间复杂度O(n)，运行时间约为 8 ms。

 

总结

解法很有技巧性，利用了贪心的思想。