柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例：

输入：heights = [2,1,5,6,2,3]

输出：10

解释：最大的矩形为图中红色区域，面积为 10

思路

遍历每个柱子，以该柱子的高度为矩形高度，并寻找每个柱子左边和右边最后一个高于它的柱子的位置作为左右矩形边界。

解法1：单调栈

int largestRectangleArea(vector<int>& heights) {
    int ans = 0;
    int n = heights.size();
    vector<int> lb(n, 0);
    vector<int> rb(n, n-1);

    stack<int> sta;
    for(int i=0;i<n;i++){
        while(!sta.empty()&&heights[i]<heights[sta.top()]){
            rb[sta.top()] = i-1;
            sta.pop();
        }
        sta.push(i);
    }
    sta.pop();
    
    for(int i=n-1;i>=0;i--){
        while(!sta.empty()&&heights[i]<heights[sta.top()]){
            lb[sta.top()] = i+1;
            sta.pop();
        }
        sta.push(i);
    }
    sta.pop();

    for(int i=0;i<n;i++) ans = max(ans, heights[i]*(rb[i]-lb[i]+1));
    return ans;
}

解法2：线段树

vector<int> a;
int tree[1000000];
void build(int p, int l, int r){
    if(l==r){
        tree[p] = a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    tree[p] = min(tree[p*2], tree[p*2+1]);
}
int query(int p, int l, int r, int x, int y){
    if(x<=l&&r<=y){
        return tree[p];
    }
    int mid = (l+r)/2;
    if(y<=mid) return query(p*2,l,mid,x,y);
    if(x>=mid+1) return query(p*2+1,mid+1,r,x,y);
    return min(query(p*2,l,mid,x,y),query(p*2+1,mid+1,r,x,y));
}
int largestRectangleArea2(vector<int>& heights) {
    a = heights;
    int n = heights.size();
    build(1,0,n-1);
    
    int ans = max(heights[0], heights[n-1]);

    int lm,rm,lb,rb;
    for(int i=0;i<=n-1;i++){
        //cout<<i<<": ("<<heights[i]<<") ";
        if(i==0) lm = heights[0];
        else lm = query(1,0,n-1,0,i-1);
        if(lm>=heights[i]){
            lb = 0;
        }else{
            int l, r, mid;
            l = 0;
            r = i-1;
            while(l<r){
                mid = (l+r)/2;
                if(query(1,0,n-1,mid+1,r)<heights[i]){
                    l = mid+1;
                }else{
                    r = mid;
                }
            }
            lb = l+1;
        }

        if(i==n-1) rm = heights[n-1];
        else rm = query(1,0,n-1,i+1,n-1);
        if(rm>=heights[i]){
            rb = n-1;
        }else{
            int l, r, mid;
            l = i+1;
            r = n-1;
            while(l<r){
                mid = (l+r)/2;
                if(query(1,0,n-1,l,mid)<heights[i]){
                    r = mid;
                }else{
                    l = mid+1;
                }
            }
            rb = l-1;
        }

        ans = max(ans, heights[i]*(rb-lb+1));
    }
    return ans;
}