Largest Rectangle in Histogram

LeetCode #84

Description:

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.

Example:

Given heights = [2,1,5,6,2,3],
return 10.

Idea:

对每个柱子，左右扩展，直到碰到比自己矮的，计算这个矩形的面积，用一个变量记录最大的面积，复杂度 O(n2 )，会超时。

这就意味着，可以维护一个递增的栈，栈里放index，每次比较栈顶与当前元素。如果当前元素大于栈顶元素，则入栈，否则说明当前元素小于栈顶，出栈并计算当前的最大面积。直至栈顶元素小于当前元素。结尾时入栈元素 0，重复计算一次。

Time: O(n)

Code:

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> s_height;
        heights.push_back(0);

        int max_area=0;
        int i=0;
        while(i<heights.size()){
            if(s_height.empty()||heights[i]>heights[s_height.top()]){
                s_height.push(i++);
            }
            else{
                int indx=s_height.top();
                s_height.pop();
                int curr_area= heights[indx]*(s_height.empty()? i : i-s_height.top()-1);
                max_area = max(curr_area, max_area);
            }
        }
        return max_area;    
    }
};

This version does not modify the input vector.

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> s_height;

        int max_area=0;
        int i=0;
        while(i<heights.size()){
            if(s_height.empty()||heights[i]>heights[s_height.top()]){
                s_height.push(i++);
            }
            else{
                int indx=s_height.top();
                s_height.pop();
                int curr_area= heights[indx]*(s_height.empty()? i : i-s_height.top()-1);
                max_area = max(curr_area, max_area);
            }
        }
        // Stack is not empty, keep pop and calculate
        while(!s_height.empty()){
            int indx=s_height.top();
            s_height.pop();
            int curr_area= heights[indx]*(s_height.empty()? i : i-s_height.top()-1);
            max_area = max(curr_area, max_area);
        }
        return max_area;    
    }
};