原题链接:

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

题目

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

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

image-20200824232413405

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

示例：

输入：[1,8,6,2,5,4,8,3,7]
输出：49

题解思路:

看到这个题目可以想到双指针的解法，但是双指针解法是否正确，会不会漏掉一些情况呢。

首先我们按着以下步骤思考：

  1. 当前两条直线是最两侧的直线，x 作为宽固定，此时取到最大值，其他的之线组合 x 逐渐缩小。
  2. 由图看出，左边线段较小，水的体积由最短的线条决定。
    1. 此时如果移动左边的边界，x 一定减小，而 h 可能最小值小，可能比最小值大。（结果待定）
    2. 此时如果移动右边的边界，x 一定减小，而 h 只有可能比最小的线段还小。 （结果不变或变小）
  3. 由此我们可以看出，只能移动较短的线条才有可能取到更大的值，依此类推，将结果遍历一次即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxArea(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int a = 0;
        while (l < r) {
            int sum = min(height[l], height[r]) * (r - l);
            a = max(a, sum);
            if (height[l] <= height[r]) {
                ++l;
            }
            else {
                --r;
            }
        }
        return a;
    }
};

/*
1.双指针
*/

image-20200825104409725