数据结构——单调栈

单调栈和单调队列

单调栈概述

1. 定义：
   单调栈是在栈的先进后出基础之上额外添加一个特性：从栈顶到栈底的元素是严格递增（or递减）。对于单调递增栈，若当前进栈元素为 e ，从栈顶开始遍历元素，把小于 e 或者等于 e 的元素弹出栈，直接遇到一个大于 e 的元素或者栈为空为止，然后再把 e 压入栈中。（包含进栈元素的附近元素的单调性）
2. 应用：
   寻找数组中最近的大于或者小于某个数的数。维持数组从0~k（包含k）的单调序列
3. 公式表达
   $$\begin{gathered} a_x>=(<=)a_y \\ (x<y) \end{gathered}$$

例题

给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。

输入格式
第一行包含整数 N，表示数列长度。

第二行包含 N 个整数，表示整数数列。

输出格式
共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。

数据范围
1≤N≤105
1≤数列中元素≤109
输入样例：
5
3 4 2 7 5
输出样例：
-1 3 -1 2 2

st = []
n = int(input())
nums = list(map(int, input().split()))
for i in range(n) :
	while len(st) and nums[i] <= st[-1] :#维护一个从栈顶到栈底单调递减的栈
		st.pop()
	if len(st) :
		print(st[-1], end = ' ')
	else :
		print(-1, end = ' ')
	st.append(nums[i])
1
2
3
4
5
6
7
8
9
10
11

N = 100010
st = [0] * N

n = int(input())
nums = list(map(int, input().split()))

k = 0
for i in range(n) :
    while k and nums[i] <= st[k] : # 找到栈中最近大于i的元素
        k -= 1
    if k : # 如果找到则输出
        print(st[k], end = ' ')
    else : # 没找到则输出-1
        print(-1, end = ' ')
    k += 1
    st[k] = nums[i] # 将当前数插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

用普通的列表就能模拟一个栈

总结

单调栈的主要思想是在保留当前遍历位的基础上，消除多余信息。在空间上进行压缩，可以在空间上找到最近。因为具有单调性，所以在空间上的最近有时也能转化为大于某个数的数的最小的数这类的查找。常与贪心结合。

单调队列概述

1. 定义：
   单调队列，即单调递减或单调递增的队列。
2. 应用：
   维护一段区间的最大值或者最小值（滑动窗口）
3. 流程：
   

例题

给定一个大小为 n≤106 的数组。

有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。

你只能在窗口中看到 k 个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。

窗口位置 最小值 最大值
[1 3 -1] -3 5 3 6 7 -1 3
1 [3 -1 -3] 5 3 6 7 -3 3
1 3 [-1 -3 5] 3 6 7 -3 5
1 3 -1 [-3 5 3] 6 7 -3 5
1 3 -1 -3 [5 3 6] 7 3 6
1 3 -1 -3 5 [3 6 7] 3 7
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式
输入包含两行。

第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。

第二行有 n 个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输出格式
输出包含两个。

第一行输出，从左至右，每个位置滑动窗口中的最小值。

第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例：
8 3
1 3 -1 -3 5 3 6 7
输出样例：
-1 -3 -3 -3 3 3
3 3 5 5 6 7

hh代表传统意义上的队尾，tt代表传统意义上的队头
q存的是下标

N = 1000010
q = [0] * N

n, k = map(int, input().split())
nums = list(map(int, input().split()))

hh, tt = 0, -1
for i in range(n) :
	if hh <= tt and q[hh] < i - k + 1 : #合法性：队列中包含元素必须在窗口内
		hh += 1
	while hh <= tt and nums[q[tt]] >= nums[i] : #单调性： 保持从队头到队尾的单调减
		tt -= 1
	tt += 1
	q[tt] = i
	if i >= k - 1 : # 如果存在一个大小为k的窗口则输出窗口最小值
		print(nums[q[hh]], end = " ")
print()

hh, tt = 0, -1
for i in range(n) :
	if hh <= tt and q[hh] < i - k + 1 :
		hh += 1
	while hh <= tt and nums[q[tt]] <= nums[i] :
		tt -= 1
	tt += 1
	q[tt] = i
	if i >= k - 1 :
		print(nums[q[hh]], end = " ")
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
28

总结

单调队列思路与单调栈类似，总的来说需要两步操作，维护合法性和维护单调性