本笔记内容来源于算法基础课

单调栈

给定一个序列，求每一个数离它最近的满足某种性质的数

暴力做法，遍历每个元素的最近最小的数，时间复杂度为$O(n^2)$

for (int i = 0; i < n; i++)
    for (int j = i - 1; j >= 0; j--)
        if (a[j] < a[i])
            break;

观察性质

对于$[0, i]$内的元素，$x < y , a_x \geq a_y$， 则$a_x$不可能作为候选结果，因为$a_y$更近且值更小，是更“好”的候选结果

因此可以维护一个候选结果的栈，而由于逆序对都不可能是候选结果，因此该栈必然是单调的，其中通常在栈中保存下标，更加通用

当遇到一个新元素，与栈顶元素进行比较，不断删除不满足单调性的栈顶元素，然后再加入新元素，从而维护单调性

如图红色为不满足单调性的栈顶元素，需弹出

模板

int tt = 0;
for (int i = 1; i <= n; i ++ ) {
    while (tt > 0 && check(stk[tt], i)) tt -- ;
    // 得到第一个满足条件的数
    stk[++tt] = i;
}

每个元素至多入栈出栈一次，时间复杂度为$O(n)$

单调队列

求滑动窗口中的最大/最小值

使用队列来维护窗口

暴力做法，遍历窗口的所有元素取最小元素，设窗口长度为$k$，时间复杂度为$O(nk)$

观察性质

对于区间$[l, r]$内的元素，$x < y , a_x \geq a_y$， 则$a_x$不可能作为候选结果，因为$a_y$在窗口中存在的时间更长且值更小，是更“好”的候选结果

因此可以维护一个候选结果的队列，而由于逆序对都不可能是候选结果，因此该队列必然是单调的，其中通常在队列中保存下标，更加通用

最小/最大元素为队头，也可在其中做二分优化

int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ ) {
    while (hh <= tt && check_out(q[hh])) hh++ ;  // 判断队头值有效且队头是否滑出窗口，队头只会向右移动一次也可以使用if
    while (hh <= tt && check(q[tt], i)) tt-- ;
    q[++tt] = i;
}