class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int len = heights.size();
        int dpL[len], dpR[len];
        dpL[0] = -1;
        dpR[len-1] = len;
        for (int i = 1; i < len; i++) {
            int& h = heights[i];
            if (h > heights[i-1]) dpL[i] = i-1;
            else {
                int j = i - 1;
                while (j >= 0 && heights[j] >= h) j = dpL[j];
                dpL[i] = j;
            }
        }
        int ret = -1;
        for (int i = len-1; i >= 0; i--) {
            int& h = heights[i];
            if (i == len - 1 || h > heights[i+1]) dpR[i] = i+1;
            else {
                int j = i + 1;
                while (j < len && heights[j] >= h) j = dpR[j];
                dpR[i] = j;
            }
            if (heights[i] * (dpR[i]-dpL[i]-1) > ret) ret = heights[i] * (dpR[i]-dpL[i]-1);
        }
        return ret;
    }
};