单调栈

模板

单调栈，可以用来求 左边/右边 第一个 大于/小于/大于等于/小于等于 当前元素的下标的位置。

模板说明：

1，求左边 ：从左往右遍历；求右边 ：从右往左遍历

2，求 < a[i] 的元素 ：维护严格递增的单调栈, a[i] <= top 作为出栈条件

求 <= a[i] 的元素 : 维护非严格递增的单调栈, a[i] < top 作为出栈条件

求 > a[i] 的元素 : 维护严格递减的单调栈, a[i] >= top 作为出栈条件

求 >= a[i] 的元素 : 维护非严格递减的单调栈, a[i] > top 作为出栈条件

// 左边第一个 < a[i] 的下标
vector<int> LeftAndStrictlyLess(int* a, int n) {
    vector<int> lf(n + 1);
    stack<int> stk;
    for(int i = 1; i <= n; i ++) {
        while(stk.size() && a[i] <= a[stk.top()]) {
            stk.pop();
        }
        lf[i] = (stk.size() ? stk.top() : -1);
        stk.push(i);
    }
    return lf;
}

// 右边第一个 < a[i] 的下标
vector<int> RightAndStrictlyGreater(int *a, int n) {
    vector<int> rt(n + 1);
    stack<int> stk;
    for(int i = n; i >= 1; i --) {
        while(stk.size() && a[i] <= a[stk.top()]) {
            stk.pop();
        }
        rt[i] = (stk.size() ? stk.top() : -1);
        stk.push(i);
    }
    return rt;
}

单调栈与DP结合

例题一：907. 子数组的最小值之和 - 力扣（LeetCode）

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 10^9 + 7 。

因为是连续子数组，考虑每个点作为右端点的所有连续子数组的 min(b) 的总和，设为 $f(x)$ 。

发现对于位置 $i$ 的元素 $a_i$ 来说，设 $lf(i)$ 表示 $a_i$ 左边第一个 $<a_i$ 的元素的位置。那么 $[lf(i)+1,i]$ 作为左端点时，min(b) 都是 $a_i$ ，因为 $a_i$ 大于等于这些元素。对于 $lf(i)$ 及其左边的位置，发现答案就是 $f(lf(i))$ 。

class Solution {
public:
    const int MOD = 1E9 + 7;
    vector<int> RightAndStrictlyGreater(vector<int> a, int n) {
        vector<int> rt(n);
        stack<int> stk;
        for(int i = 0; i < n; i ++) {
            while(stk.size() && a[i] <= a[stk.top()]) {
                stk.pop();
            }
            rt[i] = (stk.size() ? stk.top() : -1);
            stk.push(i);
        }
        return rt;
    }

    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size();
        vector<int> f(n, 0);
        vector<int> lf = RightAndStrictlyGreater(arr, n);
        for(int i = 0; i < n; i ++) {
            if(lf[i] != -1) f[i] += f[lf[i]];
            (f[i] += (i - lf[i]) * arr[i]) %= MOD;
        }
        int res = 0;
        for(int i = 0; i < n; i ++) {
            // cout << i << ' ' << lf[i] << ' ' << f[i] << '\n';
            (res += f[i]) %= MOD;
        }
        return res;
    }
};

经典 Trick 悬线法

例题一 : 84. 柱状图中最大的矩形 - 力扣（LeetCode）

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

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

这个问题比较显然，作为例题二的引入。

显然对于答案的矩形来说，它的高一定是其中一个柱子的高，因为如果比所有柱子都矮，答案还可以加一。

那么对于每个柱子 $h_i$ ，我们维护每个柱子左边第一个 $<h_i$ 的位置 $lf(i)$ ，右边第一个 $>h_i$ 的位置 $rt(i)$ 。

那么对于柱子 $i$ ，他就可以跟 $[lf(i)+1,rt(i)-1]$ 的这些位置的柱子结合为一个矩形，高度为 $h_i$ 。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> lf(n), rt(n);
        stack<int> stk;
        for(int i = 0; i < n; i ++) {
            while(stk.size() && heights[i] <= heights[stk.top()]) {
                stk.pop();
            }
            lf[i] = (stk.size() ? stk.top() : -1);
            stk.push(i);
        }
        while(stk.size()) stk.pop();
        for(int i = n - 1; i >= 0; i --) {
            while(stk.size() && heights[i] <= heights[stk.top()]) {
                stk.pop();
            }
            rt[i] = (stk.size() ? stk.top() : n);
            stk.push(i);
        }
        while(stk.size()) stk.pop();
        int maxArea = 0;
        for(int i = 0; i < n; i ++) {
            maxArea = max(maxArea, heights[i] * (rt[i] - lf[i] - 1));
        }
        return maxArea;
    }
};

例题二 : 85. 最大矩形 - 力扣（LeetCode）

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

考虑到答案矩阵一定包含一条完整的竖线。

考虑经典的技巧，悬线法。

设 $h(i,j)$ 表示从下标 $(i,j)$ 向上延伸的最大长度，要求这条竖线全部是 1 。

那么我们枚举行，对于每一行的列，假设来到了 $(x,y)$ 这个点，对于 $x$ 这一列，用单调栈维护 $h(x,y)$ 向两侧延伸的最大矩形长度，一定能枚举到答案矩形。

class Solution {
public:
    int n, m, res = 0;
    vector<vector<int> > hangLine;

    void work(int row) {
        vector<int> lf(m), rt(m);
        stack<int> stk;
        for(int j = 0; j < m; j ++) {
            while(stk.size() && hangLine[row][j] <= hangLine[row][stk.top()]) {
                stk.pop();
            }
            lf[j] = (stk.size() ? stk.top() : -1);
            stk.push(j);
        }
        while(stk.size()) {
            stk.pop();
        }
        for(int j = m - 1; j >= 0; j --) {
            while(stk.size() && hangLine[row][j] <= hangLine[row][stk.top()]) {
                stk.pop();
            }
            rt[j] = (stk.size() ? stk.top() : m);
            stk.push(j);
        }
        while(stk.size()) {
            stk.pop();
        }
        for(int j = 0; j < m; j ++) {
            res = max(res, hangLine[row][j] * (rt[j] - lf[j] - 1));
        }
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        n = matrix.size(), m = matrix[0].size(); 
        hangLine.resize(n);
        for(int i = 0; i < n; i ++) {
            hangLine[i].resize(m);
        } 
        for(int i = 0; i < n; i ++) {
            for(int j = 0; j < m; j ++) {
                if(matrix[i][j] == '1') {
                    hangLine[i][j] = (i ? hangLine[i - 1][j] + 1 : 1);
                }
            }
        }
        for(int i = 0; i < n; i ++) {
            work(i);
        }
        return res;
    }
};

双倍经验：P4147 玉蟾宫

练习题

例题一 : P6510 奶牛排队

奶牛在熊大妈的带领下排成了一条直队。

显然，不同的奶牛身高不一定相同……

现在，奶牛们想知道，如果找出一些连续的奶牛，要求最左边的奶牛 $A$ 是最矮的，最右边的 $B$ 是最高的，且 $B$ 高于 $A$ 奶牛。中间如果存在奶牛，则身高不能和 $A,B$ 奶牛相同。问这样的奶牛最多会有多少头？

从左到右给出奶牛的身高，请告诉它们符合条件的最多的奶牛数（答案可能是 $0,2$，但不会是 $1$）。

枚举右端点 $i$ ，即 $a_i=B$ ，设第一个 $\geq B$ 的位置为 $lf(i)$ ，那么 $[lf(i)+1,i-1]$ 这些位置是左端点的备选位置。

我们可以枚举这些点，设第一个 $\leq a_i$ 的位置为 $rt(i)$ ，那么只要 $rt(i)>i$ ，这个位置就是合法的。这样就得到了解法一，显然这种时间复杂度是难以解释的，虽然可以通过题目，但是我们还是希望得到拥有明确时间复杂度的解法。

考虑到 $[lf(i)+1,i-1]$ 这些位置里面，取一个最靠左的位置，满足这个位置到右端点之间，该位置的数是唯一最小值。

不动脑的想，可以维护 ST 表求最小值，最小值最靠右的位置可以用线段树求区间值域最靠右位置，这里的值域当然就是一个点了。

但是这种数据结构太大了，大过题目本身。其实就是求最靠左的最小值，而且这个最小值是最靠右最小值。我们维护一个单调严格递增栈即可，这样对栈的下标二分，分出来最左边的位置，因为是严格递增，该位置一定是最靠右的值。

解法一

constexpr int N = 1e5 + 10;
stack<int> stk1, stk2;
int n, ls[N], rs[N], a[N], ans = 0;

void solve() {
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
    }

    // l[i] 维护左边第一个 >= 的
    for(int i = 1; i <= n; i ++) {
        while(stk1.size() && a[i] > a[stk1.top()]) {
            stk1.pop();
        }
        ls[i] = (stk1.size() ? stk1.top() : 0);
        stk1.push(i);
    }

    // r[i] 维护右边第一个 <= 的
    for(int i = n; i >= 1; i --) {
        while(stk2.size() && a[i] < a[stk2.top()]) {
            stk2.pop();
        }
        rs[i] = (stk2.size() ? stk2.top() : n + 1);
        stk2.push(i);
    }

    for(int i = 1; i <= n; i ++) {
        for(int j = ls[i] + 1; j < i; j ++) {
            if(ans >= i - j + 1) break;
            if(rs[j] > i) {
                ans = i - j + 1;
            }
        }
    }
    cout << ans << '\n';
}

解法二 $O(n\log n)$

#include <bits/stdc++.h>
using namespace std;
const int N = 1E5 + 10;;

int n, ans, tx, tn;
int a[N], sx[N], sn[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (int i = 1; i <= n; ++i) {
        while (tn && a[i] <= a[sn[tn]]) -- tn;    // 严格递增单调栈 : 栈顶元素是 <    a[i] 的离 i 最近的左边的元素的下标
        while (tx && a[i] > a[sx[tx]]) -- tx;    // 递减单调栈 : 栈顶元素是 >= a[i] 的离 i 最近的左边的元素的下标
        int k = upper_bound(sn + 1, sn + 1 + tn, sx[tx]) - sn; 
        if (k != (tn + 1)) {
            ans = max(ans, i - sn[k] + 1);
        }
        sn[++ tn] = i;
        sx[++ tx] = i;
    }
    printf("%d\n", ans);
    return 0;
}

单调栈

模板