84

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int sz = heights.size(), ans=0, p;
        vector<int> leftMin(sz), rightMin(sz);

        //Find left min and right max for each index.
        leftMin[0] = -1;
        rightMin[sz-1] = sz;
        for(int i=1; i<sz; i++){
            p = i-1;
            while(p >= 0 && heights[p] >= heights[i])
                p = leftMin[p];
            leftMin[i] = p;
        }
        for(int i=sz-2; i>=0; i--){
            p = i+1;
            while(p < sz && heights[p] >= heights[i])
                p = rightMin[p];
            rightMin[i] = p;
        }

        // For each index's height, calculate the rectangle formed with that height.
        for(int i=0; i<sz; i++)
            ans = max(ans, heights[i]*(rightMin[i]-leftMin[i]-1));

        return ans;
    }
};