LeetCode-盛水容器问题（双指针解法）_给定n个非负整数表示n个连续竖直放置的方块,请计算这样的方块能装多少水。如,10 1

盛最多水的容器

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

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

分析： 这里用到了双指针法，基本的表达式: area = min(height[i], height[j]) * (j - i) 使用两个指针，值小的指针向内移动，这样就减小了搜索空间,寻求更大的高值。因为面积取决于指针的距离与值小的值乘积。如果值大的值向内移动，底距离一定减小，而求面积的另外一个乘数高一定小于等于值小的值，因此面积一定减小，而我们要求最大的面积，因此值大的指针不动，而值小的指针向内移动遍历。

class Solution {
public:
    int maxArea(vector<int>& height) {
        if(height.size() <= 1) return -1;
        int i = 0, j = height.size() - 1, res = 0;
        while(i < j){
            int h = min(height[i], height[j]);
            res = max(res, h * (j - i));
            if(height[i] < height[j]) 
          		  ++i;
            else 
            	  --j;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

分析： 求每一列的水，我们只需要关注当前列，以及左边最高的墙，右边最高的墙就够了。装水的多少，当然根据木桶效应，我们只需要看左边最高的墙和右边最高的墙中较矮的一个就够了。所以，根据较矮的那个墙和当前列的墙的高度可以分为两种种情况。

1. 较矮的墙的高度大于当前列的墙的高度。当前列的注水为 max-height。
2. 较矮的墙的高度小于等于当前列的墙的高度。当前列的注水为零。

      我们不从左和从右分开计算，我们想办法一次完成遍历。我们注意到，只要 right_max[i]>left_max[i]，积水高度将由 left_max 决定，类似的left_max[i]>right_max[i]。 所以我们可以认为如果一端有更高的条形块（例如右端），积水的高度依赖于当前方向的高度（从左到右）。当我们发现另一侧（右侧）的条形块高度不是最高的，我们则开始从相反的方向遍历（从右到左）。
我们必须在遍历时维护left_max 和right_max ，但是我们现在可以使用两个指针交替进行，实现 1 次遍历即可完成。

class Solution {
public:
    int trap(vector<int>& height)
    {
        int left = 0, right = height.size() - 1;
        int ans = 0;
        int left_max = 0, right_max = 0;
        //不计算left==right是因为最后的right点肯定是最高的列，最高的列不会有注水。
        while (left < right) {
  // height[right]大于height[left]点及其左边的列值，说明left点的left_max<right_max。
            if (height[left] < height[right]) { 
                height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]);
                ++left;
            }
  // height[left]大于height[right]点及其右边的列值，说明right点的left_max>=right_max。
            else { 
                height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]);
                --right;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23