单调栈

单调栈是一种内部元素单调的栈，可以解决“左（右）边 第一个 更大（小）的数”的问题。

单调栈的精髓实际上在于，每次向栈顶 push 新元素时，新元素显然“离得近”，如果新元素不仅“离得近”，优先级还比栈顶元素更高（更大/小），那么在以后当前栈顶元素必然不可能成为答案，因此可以将其弹出。

P4147 玉蟾宫

这道题可以转化成“柱状图中最大的矩形”的模型。我们以每一行为底，求出这个底每个位置上矩形的高度，然后求出以该行为底的柱状图中最大矩形，最大的值即为答案。

求解“柱状图中最大的矩形”常常使用单调栈来解决。首先明确，最大矩形的高一定和某一个柱的高相同，那么，对每一个柱，我们求出以该柱的高为高的矩形最大可以是多少，找它的最大值即为答案。我们只需要求出这个矩形向左右最远可以延展到哪里，也即找到左右两边第一个比这个柱更矮的柱，即可求出矩形的长。

维护一个 从栈底到栈顶严格单调递增的栈 ，每次插入元素时，如果栈为空，说明左边没有比它更小的数，反之当前栈顶即为它左边第一个更小的数。

#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e3 + 5;
char c[maxN][maxN];
int n, m, res, a[maxN][maxN];
int solve(int a[], int l) {
    int res = 0;
    stack<int> st;
    vector<int> lft(l + 1, 0), r(l + 1, 0);
    for (int i = 1; i <= l; i++) {
        while (!st.empty() && a[st.top()] >= a[i]) {
            st.pop();
        }
        if (st.empty()) {
            lft[i] = 0;
        } else {
            lft[i] = st.top();
        }
        st.push(i);
    }
    while (!st.empty()) {
        st.pop();
    }
    for (int i = l; i >= 1; i--) {
        while (!st.empty() && a[st.top()] >= a[i]) {
            st.pop();
        }
        if (st.empty()) {
            r[i] = l + 1;
        } else {
            r[i] = st.top();
        }
        st.push(i);
    }
    for (int i = 1; i <= l; i++) {
        res = max(res, (r[i] - lft[i] - 1) * a[i]);
    }
    return res;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c[i][j];
            a[i][j] = c[i][j] == 'R' ? 0 : a[i - 1][j] + 1;
        }
    }
    for (int i = 1; i <= n; i++) {
        res = max(res, solve(a[i], m));
    }
    cout << res * 3;
    return 0;
}

P2866 [USACO06NOV] Bad Hair Day S

这道题实际上是裸的求解“右边第一个小于等于该数的数”的问题，从右往左扫，维护一个 从栈底到栈顶严格单调递增的单调栈，很容易解决这个问题。

#include <bits/stdc++.h>
using namespace std;
const int maxN = 8e4 + 5;
int n, a[maxN];
long long res;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    stack<int> st;
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && a[st.top()] < a[i]) {
            st.pop();
        }
        if (st.empty()) {
            res += n - 1 - i;
        } else {
            res += st.top() - i - 1;
        }
        st.push(i);
    }
    cout << res;
    return 0;
}

P1950 长方形

和上面的第一道例题一样，考虑每一行转化成柱状图后的模型。对于每一行而言，从左往右考虑每一列，计算 右下角为这一列底部的格子 的矩形数量。

可以通过动态规划来求解，首先找到 左边第一个不高于该列高度的列，新矩形可以从那一列的“老矩形”向右延拓至当前列，从而“继承”，再考虑两列之间的矩形数量，两列之间的矩形高度都高于当前列，底乘高就可以得到这种矩形的数量。

#include <bits/stdc++.h>
using namespace std;
int n, m, h[1005][1005];
char c[1005][1005];
long long dp[1005], res;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c[i][j];
            h[i][j] = c[i][j] == '.' ? h[i - 1][j] + 1 : 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        stack<int> st;
        for (int j = 1; j <= m; j++) {
            while (!st.empty() && h[i][st.top()] > h[i][j]) {
                st.pop();
            }
            if (st.empty()) {
                dp[j] = h[i][j] * j;
            } else {
                dp[j] = 1ll * dp[st.top()] + h[i][j] * (j - st.top());
            }
            st.push(j);
            res += dp[j];
        }
    }
    cout << res;
    return 0;
}