84. Largest Rectangle in Histogram

Givennnon-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 =10unit.

For example, Given heights =[2,1,5,6,2,3], return10.

Thoughts:

1. have a stack to record increasing index

2. while current index is less that the top of the stack, update the maximum area

3. having a increasing stack is because as index gets larger, the only possible way for rectangle starting from larger index is due to its larger height value.

Code time complexity: O(n), space complexity: O(n)

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> s;
        s.push(-1);
        int ans = 0;
        int n = heights.size();
        for(int i = 0; i < n; i++){
            while((s.top()!= -1) && heights[s.top()] >= heights[i]){
                int last_idx = s.top(); s.pop();
                ans = max(ans, heights[last_idx] * (i - s.top() - 1));
            }
            s.push(i);
        }
        // reach the end of list
        while(s.top()!= -1){
            int last_idx = s.top(); s.pop();
            ans = max(ans, (heights[last_idx]) * (n - 1 - s.top()));
        }

        return ans;
    }
};

Code using 0 padding at the end and vector as stack

 class Solution {
    public:
        int largestRectangleArea(vector<int> &height) {

            int ret = 0;
            height.push_back(0);
            vector<int> index;

            for(int i = 0; i < height.size(); i++)
            {
                while(index.size() > 0 && height[index.back()] >= height[i])
                {
                    int h = height[index.back()];
                    index.pop_back();

                    int sidx = index.size() > 0 ? index.back() : -1;
                    if(h * (i-sidx-1) > ret)
                        ret = h * (i-sidx-1);
                }
                index.push_back(i);
            }

            return ret;
        }
    };

Special thanks to sipiprotoss5's for the last solution