11-container-with-most-water.md

11. Container With Most Water - 盛最多水的容器

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

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

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

 

示例:

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

---

题目标签：Array / Two Pointers

题目链接：LeetCode / LeetCode中国

题解

这题的意思就是，从数组里选择两个数，使得两者的间距与较小的那个数的乘积最大。

这题可以用暴力穷举法做，比较简单。不过，假如不暴力枚举，可以怎么做呢？

双指针夹逼法。双指针初始位于两端，然后向中间移动，每次移动高度较小的指针，期间更新最大面积。

Language	Runtime	Memory
cpp	4 ms	N/A

static auto _ = [](){
  std::ios::sync_with_stdio(false);
  std::cin.tie(NULL);
  return 0;
}();

class Solution {
public:
    int maxArea(vector<int>& height) {
        if(height.size() < 2){
            return 0;
        }
        int res = 0;
        int left = 0, right = height.size() - 1;
        while(left < right){
            res = max(res, (right-left) * min(height.at(left), height.at(right)));
            if(height.at(left) < height.at(right)){
                left++;
            }else{
                right--;
            }
        }
        return res;
    }
};