Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
Note:
https://leetcode.com/problems/trapping-rain-water/.
Example:
Example:
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
class Solution {
public:
int trap(vector<int>& height) {
stack<int> st;
int n = height.size();
int i = 0, res = 0;
while(i < n) {
if (st.empty() || height[i] <= height[st.top()]) {
st.push(i++);
}
else {
int t = st.top();
st.pop();
if (st.empty()) {
continue;
}
res += (min(height[st.top()], height[i]) - height[t]) * (i - st.top() - 1);
}
}
return res;
}
};
原文:https://www.cnblogs.com/forPrometheus-jun/p/11179595.html