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 heights = [2,1,5,6,2,3],

return 10.

思路，单调栈，维护一个递增的栈。 时间复杂度O(n)

class Solution {    public:    struct node {        int x;        int left;        int right;    };    int largestRectangleArea(vector
    
     & heights) {        vector
     
       st;        int n = heights.size();        if (n == 0) return 0;        if (n == 1) return heights[0];        vector
      
        sum(n);        for (int i = 0; i < n; ++i) {            if (i > 0) sum[i] = sum[i-1] + 1;             else sum[i] = 1;        }        int ans = 0;        for (int i = 0; i < n; ++i) {            if (st.empty() || st.back().x < heights[i]) {                st.push_back({heights[i],i,i});            } else {                int ileft = 0, iright = 0;                while (!st.empty()) {                    node v = st.back();                    if (v.x >= heights[i]) {                        st.pop_back();                        ileft = v.left;                        if (st.size()) st.back().right = v.right;                        int tmp = (sum[v.right]-sum[v.left-1])*v.x;                        if (tmp > ans) ans = tmp;                    } else break;                }                st.push_back({heights[i],ileft,i});            }                    }        while (!st.empty()) {            node v = st.back();            st.pop_back();            if (st.size()) st.back().right = v.right;            int tmp = (sum[v.right]-sum[v.left-1])*v.x;            if (tmp > ans) ans = tmp;        }        return ans;    }};
      
     
    

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