单调栈#

基本概念#

单调栈，顾名思义，这个栈是单调递增/递减的。

• 递增栈：越靠近栈顶的元素越大，如push顺序为 $1$ $2$ $3$ $4$ $5$
• 递减栈：越靠近栈底的元素越大，如push顺序为 $5$ $4$ $3$ $2$ $1$

问题引入#

P5788 【模板】单调栈

用途#

使用栈，维护一个单调的序列，通过栈顶的最值来进行计算或转移。

操作#

对于每个元素，将其和栈顶->栈底的元素一次比较，不符合的元素出栈，栈顶为当前维护的栈的最值。

例如我们要维护一个降序序列，有push顺序为 $8$ $4$ $6$ $1$ $9$ $2$ $4$ $0$

那么第i步操作后栈的状态为：$8$;$8$ $4$;$8$ $6$;$8$ $6$ $1$;$9$;$9$ $2$;$9$ $4$;$9$ $4$ $0$

1
int top = 0; // 栈顶指针初值
2
for (int i = 1; i <= n; i++) {
3
  while (top > 0 and a[q[top]] < a[i]) {
4
    cout << a[q[top]] << endl; // 输出栈顶值
5
    top--; // 栈顶出栈
6
  }
7
  q[++top] = i; // 栈顶入栈
8
}

在单调栈入栈过程中，入栈的是元素的下标，而不是元素的值。但下文为了直观，记录的是元素值，实际写题时切记要记录下标。

对于单调栈而言，记录下标不仅能获知当前元素值，还能方便获取其前后元素位置信息，这在需要回溯或计算区间问题时非常重要。此外，入栈下标后，可追踪元素更新，并在栈顶位置快速找到需要的元素，从而保持栈中数据的单调性并简化维护过程。另外，引入下标可以处理重复出现的元素，用下标作为能唯一标识一条记录的属性组。

考虑如下数组构造单调栈$a=[1,1,4,5,1,4]$，构造递增栈只记录元素的话是$[1,1,1,4]$，这个如果题目所求为输出第一个比当前元素小的元素，那可以找到，但是如果是第一个比当前元素大的元素的下标，那这时无法确定具体是第几个$1$比当前元素小。所以构造单调栈所记录的属性必须是下标，而不是元素值。

另外，在构造单调栈时，循环条件为while (top > 0 and a[q[top]] < a[i])，而不是while (top > 0 and a[q[top]] <= a[i])，循环条件是严格小于（或等于），相同元素必须全部记录，而不是当前元素小于等于栈顶元素就弹出栈顶元素。

考虑如下数组构造单调栈$a=[1,2,2,2,2,2]$，正确构造递增栈为$a=[1,2,2,2,2,2]$，可以找出第一个大于数组下标 $1$ 的元素下标为 $2$（数组从1开始）；但是如果错误记录，元素和栈顶相等的话，那构造出来时$a=[1,2]$，这个 $2$ 是最后一个$2$，下标为 $6$ ，但事实上第一个大于下标 $1$ 的元素下标为 $2$ ，是第一个 $2$ ，而不是第五个 $2$ 。

1
void solve() {
2
  int n;
3
  cin >> n;
4
  vector<int> a(n + 1), q(n + 1), ans(n + 1);
5
  for (int i = 1; i <= n; i++) {
6
    cin >> a[i];
7
  }
8
  int top = 0;
9
  for (int i = 1; i <= n; i++) {
10
    while (top > 0 and a[q[top]] < a[i]) {
11
      ans[q[top]] = i;
12
      top--;
13
    }
14
    q[++top] = i;
15
  }
16
  for (int i = 1; i <= n; i++) {
17
    cout << ans[i] << " \n"[i == n];
18
  }
19
}