动态规划、 单调栈来解决。
动态规划,就是分布看自己左右两侧最大的,取最小的与自己相减的正值即为收集到的雨水。
单调栈的思想是,从栈底到栈顶,按照坐标对应数组的值递减
如果出现不满足的情况,就进行相应的操作,即收集雨水,看代码可知
class Solution { public: 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[l],height[r]) - height[cur]; ans += h * (r - l -1 ); } st.push(i); } return ans; } };