单调栈

定义

单调栈即满足单调性的栈结构。通过只在一端进出，从而维护一个数在前 / 后的第一个大于或小于它的数。

操作 / 方式

  1. 首先按照特定的顺序遍历。
  2. 如果要求出最小值，就要将栈顶大于入列元素的所有数全部弹出。
  3. 此时候的栈顶就是直到当前下标的答案。
  4. 加入这个元素并且继续更新。

代码

结构体 + STL模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int a[N], ans[N];

struct Node { int val, idx; };
stack <Node> stk; 

signed main()
{
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = n; i >= 1; i--)
    {
        while (!stk.empty() && stk.top().val <= a[i]) stk.pop();
        ans[i] = (stk.empty() ? 0 : stk.top().idx);
        stk.push({a[i], i});
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
    return 0;
}

手写栈 + 存下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int a[N], ans[N];
int stk[N], top = 0;

signed main()
{
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = n; i >= 1; i--)
    {
        while (top && a[stk[top]] <= a[i]) top --;
        ans[i] = (top == 0 ? 0 : stk[top]);	
        stk[++ top] = i;
    }
    for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
    return 0;
}

单调队列

定义

一种通过两端弹出 / 推入 用来维护单调性质的队列，与普通队列不同，它可以用来维护区间最值问题。

原理

有一个长为 nn 的序列 aa，以及一个大小为 kk​ 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如，对于序列 [1,3,−1,−3,5,3,6,7][1,3,-1,-3,5,3,6,7] 以及 k=3k = 3，有如下过程：

窗口位置最小值最大值[1   3  -1] -3   5   3   6   7 −13 1  [3  -1  -3]  5   3   6   7 −33 1   3 [-1  -3   5]  3   6   7 −35 1   3  -1 [-3   5   3]  6   7 −35 1   3  -1  -3  [5   3   6]  7 36 1   3  -1  -3   5  [3   6   7]37\def\arraystretch{1.2} \begin{array}{|c|c|c|}\hline \textsf{窗口位置} & \textsf{最小值} & \textsf{最大值} \\ \hline \verb![1 3 -1] -3 5 3 6 7 ! & -1 & 3 \\ \hline \verb! 1 [3 -1 -3] 5 3 6 7 ! & -3 & 3 \\ \hline \verb! 1 3 [-1 -3 5] 3 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 [-3 5 3] 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 -3 [5 3 6] 7 ! & 3 & 6 \\ \hline \verb! 1 3 -1 -3 5 [3 6 7]! & 3 & 7 \\ \hline \end{array}

如果维护最小值，那么单调队列中的操作如下：

操作 状态
11 入队。 1{1}
33 比 11 大，33 入队。 1,3{1, 3}
−1-1 比所有元素都小，推出所有元素，−1-1 入队。 −1{-1}
−1-1 比所有元素都小，推出所有元素，−3-3 入队。 −3{-3}
55 比 −3-3 大，有机会，入队。 −3,5{-3, 5}
33 比 55 小，将前面大于 33 的所有数全部推出，33 入队。 −3,3{-3, 3}
−3-3 已经超过了窗口，所以 −3-3 出队，66 比 33 大，66 入队。 3,6{3, 6}
77 比 66 大，77 入队。 3,6,7{3, 6, 7}

操作方式

  1. 判断队首是否超出了边界。
  2. 在插入队尾前将不符合条件的元素全部推出。
  3. 在队尾插入新的元素。
  4. 此时对头便是以 ii​​ 为终点的区间内最值答案。

代码

结构体 + STL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct Node { int val, data; } a[N];
deque <Node> dqmax, dqmin;

int main()
{
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i].val, a[i].data = i;
    for (int i = 1; i <= n; i++)
    {
        while (!dqmin.empty() && dqmin.back().val >= a[i].val) dqmin.pop_back();
        dqmin.push_back(a[i]);
        if (dqmin.front().data == i - k) dqmin.pop_front();
        if (i >= k) cout << dqmin.front().val << ' ';  
    }
    cout << '\n';
    for (int i = 1; i <= n; i++)
    {
        while (!dqmax.empty() && dqmax.back().val <= a[i].val) dqmax.pop_back();
        dqmax.push_back(a[i]);
        if (dqmax.front().data == i - k) dqmax.pop_front();
        if (i >= k) cout << dqmax.front().val << ' ';  
    }
    return 0;
}

手写队列 + 存下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int n, k;
int a[N];
int dqmin[N], dqmax[N];

void get_min()
{
    int hh = 1, tt = 0;
    for (int i = 1; i <= n; i ++)
    {
        while (hh <= tt && dqmin[hh] <= i - k) hh ++;
        while (hh <= tt && a[dqmin[tt]] > a[i]) tt --;
        dqmin[++ tt] = i;
        if (i >= k) cout << a[dqmin[hh]] << ' ';
    }
}

void get_max()
{
    int hh = 1, tt = 0;
    for (int i = 1; i <= n; i ++)
    {
        while (hh <= tt && dqmax[hh] <= i - k) hh ++;
        while (hh <= tt && a[dqmax[tt]] < a[i]) tt --;
        dqmax[++ tt] = i;
        if (i >= k) cout << a[dqmax[hh]] << ' ';
    }
}