单调栈 | Dy_ClearSunlight

Problem’s Website

Largest Rectangle in a Histogram
City Game
Solution
这两道题都是关于单调栈，通俗来说，就是一个具有单调性的栈（如果栈都不会，请点击这）。
关于T1的解法，请见下图（摘自王婷婷-STL&基础数据结构2019.1.26）
T2其实是T1的拓展，是一个二维的单调栈，根据数据范围，θ(n^2)可以AC，于是我们可以第一次枚举第1行，第二次枚举第1-2行，第i次枚举第1-i行，一样的单调栈处理，要注意如果当前第i行第j个位置为’R’，要把表示高度的数组a[j]清零。
Code

  #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#define gc getchar()
#define ll long long
using namespace std;
int sc() {
    int xx = 0, ff = 1; char cch = gc;
    while(cch < '0' || cch > '9') {
        if(cch == '-') ff = -1; cch = gc;
    }
    while(cch >= '0' && cch <= '9') {
        xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
    }
    return xx * ff;
}
int n;
stack <int> qx;
stack <int> qy;
ll ans;
int a[100010]; 
int main() {
    while(true) {
        ans = 0;
        while(!qx.empty()) {
            qx.pop();
            qy.pop();
        }
        n = sc();
        if(!n) break; 
        for(int i = 1; i <= n; i++)
            a[i] = sc();
        a[n + 1] = 0;
        for(int i = 1; i <= n + 1; i++) {
            if(!qx.empty() && qx.top() < a[i]) {
                qx.push(a[i]); qy.push(1);
            }
            else {
                int wide = 0;
                while(!qx.empty() && qx.top() > a[i]) {
                    wide += qy.top();
                    ans = max(ans, (ll)wide * qx.top());
                    qx.pop(); qy.pop();
                }
                qx.push(a[i]); qy.push(wide + 1);
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

  #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#define gc getchar()
using namespace std;
int sc() {
    int xx = 0, ff = 1; char cch = gc;
    while(cch < '0' || cch > '9') {
        if(cch == '-') ff = -1; cch = gc;
    }
    while(cch >= '0' && cch <= '9') {
        xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
    }
    return xx * ff;
}
int n, m, ans;
int sum[1010][1010];
int a[1010];
stack <int> qx;
stack <int> qy;
int main() {
    n = sc(); m = sc();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            char c[2];
            int x = 0;
            cin >> c[0];
            if(c[0] == 'F') x = 1;
            sum[i][j] = x;
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++)
            a[j] = sum[i][j] ? a[j] + 1 : 0;
        while(!qx.empty()) {
            qx.pop(); qy.pop();
        }
        for(int j = 1; j <= m + 1; j++) {
            if(!qx.empty() && a[j] > qx.top()) {
                qx.push(a[j]); qy.push(1);
            }
            else {
                int wide = 0;
                while(!qx.empty() && qx.top() > a[j]) {
                    wide += qy.top();
                    ans = max(ans, wide * qx.top());
                    qx.pop(); qy.pop();
                }
                qx.push(a[j]); qy.push(wide + 1);
            }
        }
    }
    printf("%d\n", 3 * ans);
    return 0;
}

rp++

Problem’s Website

Solution

Code