Leetcode0011盛最多水的容器

发表于 | 分类于 ，

盛水最多的容器

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

说明：你不能倾斜容器。

示例1

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例2

输入：height = [1,1]
输出：1

示例3

输入：height = [4,3,2,1,4]
输出：16

示例4

输入：height = [1,2,1]
输出：2

提示：

  1. n == height.length
  2. 2 <= n <= 105
  3. 0 <= height[i] <= 104

解题思路

关键思路

双指针，分别指向第一个元素和最后一个元素，计算面积，移动两个元素中小值对应的指针，直至指针相遇。

具体分析

问题1：每次移动指针时，应该移动哪个？

假设有容器 h, 现有两个指针 i, j（i < j) 分别指向容器两边 h[i], h[j]，此时容器的面积为 S(i, j) 则为：

1
S(i, j) = min(h[i], h[j]) * (j − i)

容器高度由短板决定，即 h[i], h[j] 中较小的值为容器高度。

首先，不管移动哪个指针，（j - i) 一定是变小的，也就是说底边变小了，如果面积想要变大，那高度就要变大。

假设 h[i] < h[j]。

1）若移动 j, 此时面积一定是减少的：

  • 若 h[j - 1] >= h[j]，则高度为 h[i]，面积减小。
  • 若 h[i] < h[j - 1] < h[j], 则高度为 h[i]，面积减小。
  • 若 h[j] < h[i] < h[j], 则高度为 h[j - 1]，面积减小。

2）若移动 i, 面积则有可能变大：

  • 若 h[i + 1] > h[j], 则面积有可能变大
  • 若 h[i] < h[i + 1] <= h[j]，此时面积变化情况不定。
  • 若 h[i + 1] <= h[i] < h[j]，此时面积一定变小。

根据以上分析，为使面积变大，则每次应该移动 h[i]、h[j] 中较小者对应的指针。

问题2：每次移动短板时，由于会忽略掉移动的短板和其他板子所组成的面积，那这些面积中是否存在面积更大的情况，是否存在面积最大值丢失问题？

假设 h[i] < h[j]，移动 i 后，面积为 S(i+1, j)，此时我们忽略掉的面积包括：S(i, i+1)、S(i, i+2)、…、S(i, j-2)、S(i, j-1)。

首先，这些面积中的底边 （i+1 - i)、（i+2 - i)、…、（j-2 - i)、(j-1 - i) 都是小于 (j - i)的；

其次，不管 h[i+1]、h[i+2]、…、h[j-2]、h[j-1] 是不是大于 h[i]，这些面积的高度都不会比 h[i] 大，因此这些面积一定是小于 S(i, j) 的。

因此，移动的短板和其他板子组成的面积不会比当前面积大，不会存在面积最大值丢失的问题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class MaxArea {

    public int maxArea(int[] height) {
        int i = 0;
        int j = height.length - 1;
        int max = 0;
        int area = 0;
        while (i < j) {
            // S = (j - i) * min(height[i], height[j])
            if (height[i] < height[j]) {
                area = (j - i) * height[i];
                i++;
            } else {
                area = (j - i) * height[j];
                j--;
            }
            if (area > max) {
                max = area;
            }
        }
        return max;
    }

}