-------------------------------单调栈-------------------------------------

1. 模板

题目描述 : 找到 第一个 比当前数小，且在当前数前面的数

#include <iostream>
using namespace std;

const int N = 500050;

int n;
int q[N];

int main()
{
    cin >> n;
    int tt = 0;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        while (tt && q[tt] >= x) tt--;
        if (!tt) cout << "-1 ",q[++tt] = x;
        else cout << q[tt] << ' ',q[++tt] = x;
    }
}

2. 例一

题目描述 : 找到矩阵中最大的矩形的面积

原题 : 131.直方图中最大的矩形

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;

const int N = 100010;

int n;
int h[N];
int q[N];
int l[N],r[N];

int main()
{
    while (cin >> n,n)
    {
        for (int i = 1; i <= n; i ++)
            cin >> h[i];
        int tt = 0;
        q[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            while (tt && h[q[tt]] >= h[i]) tt--;
            l[i] = q[tt];
            q[++tt] = i;
        }
        tt = 0;
        q[0] = n + 1;
        for (int i = n; i >= 1; i--)
        {
            while (tt && h[q[tt]] >= h[i]) tt--;
            r[i] = q[tt];
            q[++tt] = i;
       }
        LL res = 0;
        for (int i = 1; i <= n; i++)
            res = max(res , (LL)h[i] * (r[i] - l[i] - 1));
        cout << res <<endl;
    }
    return 0;
}

3. 例二

题目描述 : 找到矩阵中面积最大的矩形

原题 : 152. 城市游戏

基本思路 : 把所以的连续的 F 转化成矩形,再用例一的解法,遍历每一行即可

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1001;

int n ,m;
int q[N] ,u[N][N];
int l[N] ,r[N];
char g[N][N];

int work(int h[])
{
    h[0] = h[m + 1] = -1; // 保险起见

    int tt = 0; 
    q[0] = 0;
    for (int i = 1; i <= m; i++)
    {
        while (tt && h[q[tt]] >= h[i]) tt--;
        l[i] = q[tt];
        q[++ tt] = i;
    }

    tt = 0;
    q[0] = m + 1;
    for (int i = m; i >= 1; i--)
    {
        while (tt && h[q[tt]] >= h[i]) tt--;
        r[i] = q[tt];
        q[++ tt] = i;
    }

    int res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res , h[i] * (r[i] - l[i] - 1));

    return res * 3;
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            cin >> g[i][j];
            int up = i;
            while (up >= 1 && g[up --][j] == 'F') u[i][j] ++;
        }

    int res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res , work(u[i]));

    cout << res;
    return 0;
}

3. 例三

题目描述 : 找一个矩阵挖掉一个格子后最大的矩形面积

原题 : 3516. 最大面积

基本思路 : 对这个挖掉的格子的 上下左右 四个部分 分别求一次矩形最大面积

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 2002;

int n, m;
char g[N][N];
int U[N], D[N], L[N], R[N];
int s[N][N] ,q[N], l[N], r[N];

int work(int h[],int n)
{
    h[0] = h[n + 1] = -1;

    int tt = 0;
    q[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        while (h[q[tt]] >= h[i]) tt--;
        l[i] = q[tt];
        q[++ tt] = i;
    }

    tt = 0;
    q[0] = n + 1;
    for (int i = n; i >= 1; i--)
    {
        while (h[q[tt]] >= h[i]) tt--;
        r[i] = q[tt];
        q[++ tt] = i;
    }

    int res = 0;
    for (int i = 1; i <= n; i++)
        res = max(res , h[i] * (r[i] - l[i] - 1));

    return res;
}

void init()
{
    memset(s , 0 , sizeof s);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            if (g[i][j] == '1') s[i][j] = s[i - 1][j] + 1;
            else s[i][j] = 0;
        U[i] = max(U[i - 1] , work(s[i] , m));
    }

    memset(s , 0 , sizeof s);
    for (int i = n; i; i--)
    {
        for (int j = 1; j <= m; j++)
            if (g[i][j] == '1') s[i][j] = s[i + 1][j] + 1;
            else s[i][j] = 0;
        D[i] = max(D[i + 1] , work(s[i] , m));
    }

    memset(s , 0 , sizeof s);
    for (int i = 1; i <= m; i ++)
    {
        for (int j = 1; j <= n; j++)
            if (g[j][i] == '1') s[i][j] = s[i - 1][j] + 1;
            else s[i][j] = 0;
        L[i] = max(L[i - 1] , work(s[i] , n));
    }

    memset(s , 0 , sizeof s);
    for (int i = m; i; i--)
    {
        for (int j = 1; j <= n; j++)
            if (g[j][i] == '1') s[i][j] = s[i + 1][j] + 1;
            else s[i][j] = 0;
        R[i] = max(R[i + 1] , work(s[i] , n));
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf ("%s",g[i] + 1);

    init();

    int Q;
    cin >> Q;
    while ( Q-- )
    {
        int x,y;
        cin >> x >> y;
        x ++,y ++;
        cout << max(max(U[x - 1] , D[x + 1]) , max(L[y - 1] , R[y + 1])) << endl;
    }
    return 0;
}