题目
给定 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
解题
方法一：双指针（超时）
查找当前位置（比如索引4）左右的最大高度，左（索引3），右（索引7）
由于接水取决于两侧最小高度，那么h=min(lHeight,rHeight)-height[i];
class Solution { public: int trap(vector<int>& height) { int res=0; for(int i=0;i<height.size();i++){ if(i==0||i==height.size()-1) continue; int lHeight=height[i]; int rHeight=height[i]; for(int l=i-1;l>=0;l--){ lHeight=max(lHeight,height[l]); } for(int r=i+1;r<height.size();r++){ rHeight=max(rHeight,height[r]); } int h=min(lHeight,rHeight)-height[i]; if(h>0) res+=h; } return res; } };
方法二：动态规划
和方法一 一样的思想，只不过用两个数组记录了每个柱子的左边最大高度和右边最大高度
class Solution { public: int trap(vector<int>& height) { int n=height.size(); vector<int> maxLeft(n,0); vector<int> maxRight(n,0); // 记录每个柱子左边柱子最大高度 maxLeft[0]=height[0]; for(int i=1;i<n;i++){ maxLeft[i]=max(height[i],maxLeft[i-1]); } // 记录每个柱子右边柱子最大高度 maxRight[n-1]=height[n-1]; for(int i=n-2;i>=0;i--){ maxRight[i]=max(height[i],maxRight[i+1]); } // 求和 int res=0; for(int i=0;i<n;i++){ int h=min(maxLeft[i],maxRight[i])-height[i]; if(h>0) res+=h; } return res; } };
方法三：单调栈
利用单调栈，按照行计算
情况一：height[i] 入栈
情况二：height[i]==height[i-1] 将一样高度的先出栈，把最新的入栈 ，防止 按照行计算的时候重复计算
情况三：height[i]>height[i-1] 凹槽出现，按照行进行计算
class Solution { public: int trap(vector<int>& height) { if (height.size() <= 2) return 0; // 可以不加 stack<int> st; // 存着下标，计算的时候用下标对应的柱子高度 st.push(0); int sum = 0; for (int i = 1; i < height.size(); i++) { if (height[i] < height[st.top()]) { // 情况一 st.push(i); } if (height[i] == height[st.top()]) { // 情况二 st.pop(); // 其实这一句可以不加，效果是一样的，但处理相同的情况的思路却变了。 st.push(i); } else { // 情况三 while (!st.empty() && height[i] > height[st.top()]) { // 注意这里是while int mid = st.top(); st.pop(); if (!st.empty()) { int h = min(height[st.top()], height[i]) - height[mid]; int w = i - st.top() - 1; // 注意减一，只求中间宽度 sum += h * w; } } st.push(i); } } return sum; } };
简洁的一种
if (st.empty()) break;使得 最左侧不能装水
最后遍历完后stack依然不是空的，这样使得最右侧，不能装水
int trap(vector<int>& height) { int ans = 0; stack<int> st; for (int i = 0; i < height.size(); i++) { while (!st.empty() && height[st.top()] < height[i]) { int cur = st.top(); st.pop(); if (st.empty()) break; int l = st.top(); int r = i; int h = min(height[r], height[l]) - height[cur]; ans += (r - l - 1) * h; } st.push(i); } return ans; }
