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. For example, Given height = [2,1…

leetcode_largest_rectangle_in_histogram.cpp

#define MAXN 1000000

int st[MAXN];
int l[MAXN];
int r[MAXN];

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        int n = height.size();
        int id = -1;
        for (int i = 0; i < n; ++i) {
            while (id != -1) {
                if (height[st[id]] >= height[i])
                    id--;
                else
                    break;
            }
            l[i] = (id == -1 ? -1 : st[id]) + 1;
            st[++id] = i;
        }
        id = -1;
        for (int i = n - 1; i >= 0; --i) {
            while (id != -1) {
                if (height[st[id]] >= height[i])
                    id--;
                else
                    break;
            }
            r[i] = (id == -1 ? n : st[id]) - 1;
            st[++id] = i;
        }
        int ret = 0;
        for (int i = 0; i < n; ++i)
            ret = max(ret, (r[i] - l[i] + 1) * height[i]);
        return ret;
    }
};