Coding Caprice - monotonic stack2

42. 接雨水

class Solution {
public:int trap(vector<int>& height) {stack<int> sh;int out = 0;for(int i=0; i<height.size(); ++i){while(!sh.empty() && height[sh.top()]<height[i]){int bo = height[sh.top()];sh.pop();if(sh.empty()){break;}int ht = min(height[sh.top()], height[i]);out += (ht - bo) * (i-sh.top()-1);}sh.push(i);}return out;}
};

84. 柱状图中最大的矩形

class Solution {
public:int largestRectangleArea(vector<int>& heights) {stack<int> st;int num = heights.size();vector<int> rr(num, num);for(int i=0; i<num; ++i){while(!st.empty() && heights[i]<heights[st.top()]){rr[st.top()] = i;st.pop();}st.push(i);}while(!st.empty()){st.pop();}vector<int> ll(num, -1);for(int i=num-1; i>=0; --i){while(!st.empty() && heights[i]<heights[st.top()]){ll[st.top()] = i;st.pop();}st.push(i);}int out = 0;for(int i=0; i<num; ++i){out = max(out, heights[i] * (rr[i] - ll[i] - 1));}return out;}
};

• 单调栈是找出右/左边第一个比自己低/高的值或者id