84 Largest Rectangle in Histogram

Solution

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        if ( n == 0 ) return 0;
        if ( n == 1 ) return heights[0];
        vector<int> left(n, 0);
        stack<int> s;
        s.push(0);
        for ( int i = 1; i <= n-1; i++ ) {
            while ( ! s.empty() and heights[s.top()] >= heights[i] ) s.pop();
            if ( ! s.empty() ) left[i] = s.top() + 1;
            s.push(i);
        }
        while ( ! s.empty() ) s.pop();
        s.push(n-1);
        int maxS = heights[n-1]*(n-left[n-1]);
        for ( int i = n-2; i >= 0; i-- ) {
            while ( ! s.empty() and heights[s.top()] >= heights[i] ) s.pop();
            if ( s.empty() ) maxS = max(maxS, heights[i] * (n-left[i]));
            else maxS = max(maxS, heights[i]*(s.top() - left[i]));
            s.push(i);
        }
        return maxS;
    }
};

Notes
I can almost memorize the solution, but the important thing is to understand why this method works!

• The array left here is to record the left most position the current height can extend. (i.e. height[i] can extend at most to left[i]).
• Determining left[i] is equivalent to looking for the largest index j such that hights[j] < hights[i]. Then left[i] = j+1.
• We maintain a stack that records the monotonously increasing height. Once a new height heights[i] is examined, pop out all the larger heights from the top of the stack until we find that heights[s.top()] < heights[i] or the stack is empty. Then left = s.top()+1 (or left = 0 if the stack is empty). Then we push this height to the stack.
• Use the same trick to scan from the right, and evaluate the area at the same time.