算法第48天｜单调栈：42. 接雨水、84.柱状图中最大的矩形

42. 接雨水

题目

思路与解法

class Solution {
public:int trap(vector<int>& height) {stack<int> st;st.push(0);int res = 0;for(int i=1;i<height.size();i++){if(height[i] <= height[st.top()]){st.push(i);}else if(height[i] > height[st.top()]){while(!st.empty() && height[i] > height[st.top()]){int mid = height[st.top()];st.pop();if(!st.empty()){int h = min(height[st.top()], height[i]);res += (h-mid)*(i - st.top() - 1);}}st.push(i);}}return res;}
};

84.柱状图中最大的矩形

题目

思路与解法

class Solution {
public:int largestRectangleArea(vector<int>& heights) {stack<int> st;heights.insert(heights.begin(), 0);heights.push_back(0);st.push(0);int res = 0;for(int i=1;i<heights.size();i++){if(heights[i] >= heights[st.top()]){st.push(i);}else if (heights[i] < heights[st.top()]){while(!st.empty() && heights[i] < heights[st.top()]){int mid = st.top();st.pop();int left = st.top();int right = i;int h = heights[mid];int area = h * (right - left -1);res = res > area ? res:area; }st.push(i);}}return res;}
};