84. Largest Rectangle in Histogram
Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
For example, Given heights = [2,1,5,6,2,3], return 10.
解题思想很简单的一道题。
用单调队列来维护长方体的高度与宽度。（用高度从小到大排）
每当有一个新的长方体H加入，就将队列中比H高的其他长方体pop出去。
在pop的过程中要注意传递宽度。
细节：pop的过程中，宽度要传递到：队列中上一个长方体以及新长方体H之间高度较大的那一个。
class Solution { public: int ans; int largestRectangleArea(vector<int>& heights) { ans=0; stack<pair<int,int> > sta; for(int i=0;i<heights.size();i++) { int x = heights[i]; Push(sta,x); } Push(sta,0); return ans; } void Add(pair<int,int> &now, int x) { now.second += x; ans = max(ans , now.first * now.second ); } void Push(stack<pair<int,int> > &sta, int x) { pair< int , int > X = make_pair(x,1); Add(X,0); while(!sta.empty() && sta.top().first > x) { pair<int,int> Pre = sta.top(); sta.pop(); ans = max( ans , Pre.first * Pre.second ); if(!sta.empty() && sta.top().first > x) Add(sta.top(),Pre.second); else Add(X,Pre.second); } if(!sta.empty() && sta.top().first == x) Add(sta.top(),X.second); else sta.push(X); } };
