84. Largest Rectangle in Histogram

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.

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

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();

        int L[n], R[n], st[n];

        int t = 0;
        for(int i = 0; i < n; i++){
            while(t > 0 && heights[ st[ t - 1] ]>= heights[i])    t--;

            L[i] = t == 0? 0 : (st[t - 1] + 1);
            st[t++] = i;
        }

        t = 0;
        for(int i = n - 1; i >= 0; i--){
            while(t > 0 && heights[ st[t - 1] ] >= heights[i]) t--;
            R[i] = t == 0 ? n: st[t - 1];
            st[t++] = i;
        }

        int res =0;
        for(int i = 0; i < n; i++){
            res = max(res, heights[i]*(R[i] - L[i]));
        }

        return res;
    }
};