Leet Code: Problem #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.

 

Example:

Input: [2,1,5,6,2,3]
Output: 10

Solution in C++:
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
		int n = heights.size();
		if (!n) return 0;        
        heights.push_back(0);
        stack<int>stk;
		int res = 0;		
		for (int i = 0; i < heights.size(); i++) {
            //cout<<heights[stk.top()]<<" - "<<heights[i]<<endl;
		while (!stk.empty() && heights[stk.top()] > heights[i]) {                
                    int h = heights[stk.top()];
                    stk.pop();
                    int l = stk.empty() ? 0 : stk.top()+1;
                    res = max(res, (i-l)*h);
		    }
		stk.push(i);
		}
		return res;
    }
};