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

---

题目思路

---

代码

class Solution {
public:int largestRectangleArea( vector<int>& h ) {int n = h.size();vector<int> left( n ), right( n );stack<int> st;// 求每个矩形的第一个小于左边界的矩形 - 用单调栈for ( int i = 0; i < n; ++i ) {while ( st.size() && h[st.top()] >= h[i] ) st.pop();if ( st.empty() ) left[i] = -1;else left[i] = st.top();st.push( i );}// 求每个矩形的第一个小于右边界的矩形 - 用单调栈st = stack<int>(); // 清空栈for ( int i = n - 1; i >= 0; --i ) {while ( st.size() && h[st.top()] >= h[i] ) st.pop();if( st.empty() ) right[i] = n;else right[i] = st.top();st.push( i );}// 遍历维护 最大值int ret = 0;for (int i = 0; i < n; ++i) ret = max( ret, (right[i] - left[i] - 1) * h[i] );return ret;}
};