无标题
题目：
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：
- n == height.length
- 1 <= n <= 2 * 104
- 0 <= height[i] <= 105
解法一：暴力
逐个计算每一列能存下的水量。
遍历整个数组。针对数组中的每个元素arr[i]，都分别向左、向右遍历一遍数组，找到arr[i]左侧和右侧的最大值，计为leftMax和rightMax，如果leftMax <= arr[i]或者rightMax <= arr[i]，说明当前这一列存不出水。否则当前列能存储的水量为min(leftMax, rightMax) - arr[i]。
所以数组的i位置能存储的水量res[i] = max{0, min{max(arr[0...i-1]), max(arr[i+1...n])} - arr[i] }。
再思考一下，如果max(arr[0...i-1]) > arr[i]，那么数组0到i-1位置的最大值和0到i位置的最大值一定是相等的；如果max(arr[0...i-1]) <= arr[i]，那么数组0到i位置的最大值一定等于arr[i]，所以为了避免和0之间取max的计算，上述公式可以化简为下面的形式。res[i] = min{max{arr[0... i]} , max{arr[i . . . n − 1]}} − arr[i]int trap(vector<int>& height) {
int sum = 0;
int n = height.size();
for (int i=0; i<n; i++) {
int leftMax = 0;
for (int j=0; j<=i; j++) {
if (height[j] > leftMax) {
leftMax = height[j];
}
}
int rightMax = 0;
for (int j=i; j<n; j++) {
if (height[j] > rightMax) {
rightMax = height[j];
}
}
sum += min(leftMax, rightMax) - height[i];
}
return sum;
}
解法二：双指针
从暴力解法中我们可以看到，要求数组i位置可以存储的水量，需要先求出0到i位置的最大值max(arr[0...i])，再求出i到n-1位置的最大值max(arr[i...n-1])，两个值中取最小与arr[i]做差。
暴力解法之所以时间复杂度比较差，是因为对于数组中的每一个元素，都需要再遍历一遍数组才能得到它左右两侧的最大值。
所以我们可以通过预处理数组得到leftMax[]和rightMax[]两个数组，leftMax[i]代表数组0到i位置的最大值，leftMax[i] = max(leftMax[i-1], arr[i])；rightMax[i]代表数组i位置到n-1位置的最大值，rightMax[i] = max(rightMax[i+1], arr[i])。
这样我们就得到了如下的算法流程。
首先遍历数组，从左向右得到数组leftMax[]，再从右向左得到rightMax[]。然后再遍历一遍数组，对于数组的每一个位置i，通过leftMax[i]，rightMax[i]和arr[i]得到结果，将结果汇总得到的值就是最终答案。int trap(vector<int>& height) {
int n = height.size();
vector<int> leftMax(n, 0);
leftMax[0] = height[0];
for (int i=1; i<n; i++) {
leftMax[i] = max(leftMax[i-1], height[i]);
}
vector<int> rightMax(n, 0);
rightMax[n-1] = height[n-1];
for (int i=n-2; i>=0; i--) {
rightMax[i] = max(rightMax[i+1], height[i]);
}
int res = 0;
for (int i=0; i<n; i++) {
res += min(leftMax[i], rightMax[i]) - height[i];
}
return res;
}
解法三：双指针进阶
解法二中的双指针需要遍历三次数组，第一次得出数组leftMax[]，第二次得出数组rightMax[]，第三次才是根据leftMax[i]，rightMax[i]和height[i]得出结果。那我们能不能想办法把这三次遍历合并成一次呢？
我们设置两个指针，left指向数组的0位置，right指针指向数组的n-1位置。再使用两个变量leftMax和rightMax，leftMax的含义是数组0...left位置的最大值，rightMax的含义是数组right...n-1位置的最大值，这几个变量设置好后就有以下几种情况。
leftMax < rightMax，此时可以使用leftMax来结算height[left]位置的储水量。它的右侧可能还会有比rightMax更高的元素，但不会影响left位置的储水量。因为这种情况下left位置左侧的最大值是影响该位置储水量的瓶颈，此时res[left] = leftMax - height[left]。leftMax > rightMax，此时可以使用rightMax来结算right位置的储水量。同样的，它的左侧可能还会有比leftMax更高的元素，但都不影响right位置的储水量。因为这种情况下right位置右侧的最大值是影响该位置储水量的瓶颈。此时res[right] = rightMax - height[right]。leftMax == rightMax，此时既可以结算左侧，也可以结算右侧，或者左右两侧可以同时结算储水量。res[left] = leftMax - height[left]，res[right] = rightMax - height[right]。但是要注意如果结算前left == right，此时只能结算一侧。
不断重复上述流程，哪侧结算就将哪侧的指针相应移动，并在移动的过程中更新leftMax和rightMax，直到两个指针会合，结算完最后一个位置的水量为止。
class Solution { |