LeetCode - 11 - Container With Most Water

时间:2022-12-29 14:16:36

题目

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

LeetCode - 11 - 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(n2),运行时间约为 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

 

总结

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