*算法训练（leetcode）第四十二天 | 42. 接雨水、84. 柱状图中最大的矩形

*42. 接雨水

leetcode题目地址

单调栈存储柱子下标。栈顶到栈底单调递增。

1. 当新访问的元素大于栈顶指向元素时，取栈顶指向元素作为中间柱子，栈顶弹出，下一个栈顶指向元素做左侧柱子，当前访问元素做右侧柱子，计算三个柱子中间所接雨水量。重复迭代上述操作直至栈顶元素大于当前元素。最后将当前元素下标放入栈中
2. 当新访问元素等于栈顶指向元素时，栈顶弹出将当前元素存入。因为当有两个相同柱子做左边界时，需要取相同柱子里的右侧作为左边界。
3. 当新访问元素小于栈顶指向元素时，将当前元素存入栈中。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

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

*84. 柱状图中最大的矩形

leetcode题目地址

单调栈存储柱子下标。栈顶到栈底单调递减。

在原数组首位各插入一个0.

1. 当访问元素大于栈顶指向元素时，直接放入栈中。
2. 当访问元素与栈顶指向元素相等时，弹出栈顶，将当前元素放入栈中。
3. 当访问元素小于栈顶指向元素时，取栈顶指向元素为中间柱子，弹出栈顶，下一个栈顶指向元素为左边柱子，当前访问元素为右边柱子，计算面积。重复上述过程直至访问元素大于等于栈顶指向元素。

题解思路

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// c++
class Solution {
public:int largestRectangleArea(vector<int>& heights) {stack<int> st;int result = heights[0];st.push(0);heights.insert(heights.begin(), 0);heights.push_back(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()]){st.pop();st.push(i);}else {while(!st.empty() && heights[i] < heights[st.top()]){int mid = st.top();st.pop();if(!st.empty()){int left =  st.top();int w = heights[mid];int h = i - left - 1;result = max(result, w*h);}}st.push(i);}}return result;}
};