Leetcode11-盛最多水的容器

1. 题目描述

题目链接

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

示例 1：

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

2. 思考

首先思考本题如何去获取最大面积矩形，如果直接暴力枚举，那么时间复杂度为O(n2)，很明显是不划算的，实际上我们就是在尝试每一种两条边的组合。那么我们尝试用双指针来代表矩形的两条边。如果控制双指针从宽较小的矩形逐渐到宽较大的矩形，这样不好处理，因为宽小的矩形更多，想象一个搜索过程，我们应该从较少的节点出发，扩展到较多的节点。所以我们需要从宽较大的矩形（数量较少），逐渐缩小到宽较小的矩形（数量较多），在这个过程中去检查最大矩形面积。
那么很明确了，双指针从高度数组两端出发，每次选择一个指针往中间移动一格，代表矩形宽减少1，直到两指针相遇。那么选择哪一边的指针往中间移动呢？这是有讲究的，如果我们选择指向更高柱子的那个指针向中间移动，那么新得到的矩形面积一定不会比原来的矩形面积大，这是因为矩形的面积是由宽 * min(左边柱子高，右边柱子高)计算得到的，在指向更低的柱子的那个指针没有移动的情况下，新得到的矩形的有效高度肯定不会比这个更低柱子要高，而由于宽度减小了，那么其面积一定是减小了。因此我们不应该将指向更高柱子的那个指针向中间移动，所以我们选择将指向更低柱子的那个指针向中间移动。重复这个过程，并不断更新最大矩形面积，直到两指针错开，那么我们就得到答案。

3.代码实现

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