【leetcode面试经典150题】16.接雨水（C++）

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主，题解使用C++语言。（若有使用其他语言的同学也可了解题解思路，本质上语法内容一致）

【题目描述】

给定 n 个非负整数表示每个宽度为 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 个单位的雨水（蓝色部分表示雨水）。 

【示例二】

输入：height = [4,2,0,3,2,5]
输出：9

【提示及数据范围】

• n == height.length
• 1 <= n <= 2 * 10的4次方
• 0 <= height[i] <= 10的5次方

【代码】

// 方法一：动态规划// 对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值，
// 下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]。
// 创建两个长度为 n 的数组 leftMax 和 rightMax。
// 对于 0≤i<n，leftMax[i] 表示下标 i 及其左边的位置中，height 的最大高度，
// rightMax[i] 表示下标 i 及其右边的位置中，height 的最大高度。// leftMax[0]=height[0]，rightMax[n−1]=height[n−1]。两个数组的其余元素的计算如下：// 当 1≤i≤n−1 时，leftMax[i]=max⁡(leftMax[i−1],height[i])；// 当 0≤i≤n−2 时，rightMax[i]=max⁡(rightMax[i+1],height[i])。// 因此可以正向遍历数组 height 得到数组 leftMax 的每个元素值，
// 反向遍历数组 height 得到数组 rightMax 的每个元素值。// 在得到数组 leftMax 和 rightMax 的每个元素值之后，
// 对于 0≤i<n，下标 i 处能接的雨水量等于 min⁡(leftMax[i],rightMax[i])−height[i]。
// 遍历每个下标位置即可得到能接的雨水总量。class Solution {
public:int trap(vector<int>& height) {int n = height.size();if (n == 0) {return 0;}vector<int> leftMax(n);leftMax[0] = height[0];for (int i = 1; i < n; ++i) {leftMax[i] = max(leftMax[i - 1], height[i]);}vector<int> rightMax(n);rightMax[n - 1] = height[n - 1];for (int i = n - 2; i >= 0; --i) {rightMax[i] = max(rightMax[i + 1], height[i]);}int ans = 0;for (int i = 0; i < n; ++i) {ans += min(leftMax[i], rightMax[i]) - height[i];}return ans;}
};//方法二：单调栈// 维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 height 中的元素递减。// 从左到右遍历数组，遍历到下标 i 时，如果栈内至少有两个元素，记栈顶元素为 top
// top 的下面一个元素是 left，则一定有 height[left]≥height[top]。// 如果 height[i]>height[top]，则得到一个可以接雨水的区域，该区域的宽度是 i−left−1，
// 高度是 min⁡(height[left],height[i])−height[top]，
// 根据宽度和高度即可计算得到该区域能接的雨水量。// 为了得到 left，需要将 topp 出栈。在对 top 计算能接的雨水量之后，left 变成新的 top，
// 重复上述操作，直到栈变为空，或者栈顶下标对应的 height 中的元素大于或等于 height[i]。// 在对下标 i 处计算能接的雨水量之后，将 i 入栈，
// 继续遍历后面的下标，计算能接的雨水量。遍历结束之后即可得到能接的雨水总量。class Solution {
public:int trap(vector<int>& height) {int ans = 0;stack<int> stk;int n = height.size();for (int i = 0; i < n; ++i) {while (!stk.empty() && height[i] > height[stk.top()]) {int top = stk.top();stk.pop();if (stk.empty()) {break;}int left = stk.top();int currWidth = i - left - 1;int currHeight = min(height[left], height[i]) - height[top];ans += currWidth * currHeight;}stk.push(i);}return ans;}
};// 方法三：双指针//维护两个指针 left 和 right，以及两个变量 leftMax 和 rightMax，
// 初始时 left=0,right=n−1,leftMax=0,rightMax=0。
// 指针 left 只会向右移动，指针 right 只会向左移动，
// 在移动指针的过程中维护两个变量 leftMax 和 rightMax 的值。// 当两个指针没有相遇时，进行如下操作：// 使用 height[left] 和 height[right] 的值更新 leftMax 和 rightMax 的值；// 如果 height[left]<height[right]，则必有 leftMax<rightMax，
// 下标 left 处能接的雨水量等于 leftMax−height[left] 处能接的雨水量加到能接的雨水总量，
// 然后将 left 加 1（即向右移动一位）；// 如果 height[left]≥height[right]，则必有 leftMax≥rightMax，
// 下标 right 处能接的雨水量等于 rightMax−height[right]，
// 将下标 right 处能接的雨水量加到能接的雨水总量，然后将 right 减 1（即向左移动一位）。// 当两个指针相遇时，即可得到能接的雨水总量。class Solution {
public:int trap(vector<int>& height) {int ans = 0;int left = 0, right = height.size() - 1;int leftMax = 0, rightMax = 0;while (left < right) {leftMax = max(leftMax, height[left]);rightMax = max(rightMax, height[right]);if (height[left] < height[right]) {ans += leftMax - height[left];++left;} else {ans += rightMax - height[right];--right;}}return ans;}
};