柱状图中最大的矩形
单调栈
我们可以遍历每根柱子，以当前柱子 i 的高度作为矩形的高，那么矩形的宽度边界即为向左找到第一个高度小于当前柱体 i 的柱体，向右找到第一个高度小于当前柱体 i 的柱体。
- 和42接雨水类似
为什么这么说呢，42. 接雨水 (opens new window)是找每个柱子左右两边第一个大于该柱子高度的柱子，而本题是找每个柱子左右两边第一个小于该柱子的柱子。 - 那么因为本题是要找每个柱子左右两边第一个小于该柱子的柱子，所以从栈头（元素从栈头弹出）到栈底的顺序应该是从大到小的顺序！
- 只有栈里从大到小的顺序，才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。
- 所以本题单调栈的顺序正好与接雨水反过来。
- 此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度
class Solution { public: int largestRectangleArea(vector<int>& heights) { heights.insert(heights.begin(), 0); // 数组头部加入元素0 heights.push_back(0); // 数组尾部加入元素 stack<int> st; int result = 0; st.push(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()==0 && heights[i] < heights[st.top()] ) { int mid = st.top(); st.pop(); if(st.empty()==0) { int left = st.top(); int right = i; int sum = (right - left -1) * heights[mid]; cout<<left<<' '<<mid<<' '<<right<<' '<<sum<<endl; if(sum > result) result = sum; } } st.push(i); } } return result; } };
二刷（逐层计算 超时）
class Solution { public: int largestRectangleArea(vector<int>& heights) { int result = 0; int max_h = 0; for(int i=0 ; i<heights.size() ;i++) if(heights[i] > max_h) max_h = heights[i]; for(int H=1 ; H<=max_h ;H++) { int tmp_result = 0; for(int i=0 ; i<heights.size() ;i++) { if(heights[i] >= H) { tmp_result += H; if(tmp_result > result) result = tmp_result; }else tmp_result = 0; } } return result; } };
二刷（单调栈）
class Solution { public: int largestRectangleArea(vector<int>& heights) { heights.insert(heights.begin() , 0); heights.push_back(0); stack<int> my_stack; int result = 0; my_stack.push(0); for(int i=1 ; i<heights.size() ;i++) { if(heights[i] > heights[my_stack.top()]) { my_stack.push(i); } else if(heights[i] == heights[my_stack.top()]) { my_stack.pop(); my_stack.push(i); }else if(heights[i] < heights[my_stack.top()]) { while(my_stack.size() != 0 && heights[i] < heights[my_stack.top()]) { int mid = my_stack.top(); my_stack.pop(); if(my_stack.size() != 0) { int left = my_stack.top(); int right = i; result = max(result , (right - left - 1) * heights[mid] ); } } my_stack.push(i); } } return result; } };
