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 height = [2,1,5,6,2,3],
return 10.

tag: array, stack

趁热打铁，刚写完上篇关于计算最大子矩阵的问题，中间用到了这个计算最大直方图面积的问题，于是就写了这题。一遍AC。

利用一个stack，维护递增的序列，边界情况特殊考虑。

C++:

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        stack<int> s;
        int i = 0;
        int maxArea = 0;
        if(height.empty()){
            return 0;
        }
        while(i < height.size()){
            if(s.empty() || height[s.top()] <= height[i]){
                s.push(i);
                i++;
            }   
            //s is not empty, height[i] < height[s.top()]
            else{
                int t = s.top();
                s.pop();
                int start = s.empty()?-1:s.top();
                int thisArea = height[t] * (i - start - 1);
                maxArea = max(thisArea, maxArea);
            }
        }
        //i at the (end + 1) position of vector
        while(!s.empty()){
            int t = s.top();
            s.pop();
            int start = s.empty()?-1:s.top();
            int thisArea = height[t] * (height.size() - start - 1);
            maxArea = max(thisArea, maxArea);
        }
        return maxArea;    
    }
};