单调队列是一种特殊的数据结构，类比于队列，它具有一种单调性，即队列中的元素单调递增或者单调递减。
单调队列
我们理解单调队列之前先要理解什么是双端队列，一般的队列只能一端进一端出，而双端队列则是在两端都可以进行进队出队的操作。
而单调队列的入队方式同样也是在队尾添加元素，不过需要将前面的比其小的元素都删除。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
type dqueue []int
func (d *dqueue) Push(x int) {
for len(*d) != 0 && (*d)[len(*d)-1] < x {
// 移除前面比该值小的数
*d = (*d)[:len(*d)-1]
}
*d = append(*d, x)
}
func (d *dqueue) Max() int {
if len(*d) == 0 {
return -1
}
return (*d)[0]
}
func (d *dqueue) Pop(n int) {
if len(*d) != 0 && (*d)[0] == n {
*d = (*d)[1:]
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
func maxSlidingWindowQueue(nums []int, k int) []int {
// 使用单调队列或者是 优先队列 优先队列存储的索引，但是按照的是最大值进行的排序
res := make([]int, 0)
i, j := 0, 0
q := make(dqueue, 0)
for j <= len(nums) {
if j-i < k {
q.Push(nums[j])
} else {
t := nums[i]
res = append(res, q.Max())
q.Pop(t)
if j < len(nums) {
q.Push(nums[j])
}
i++
}
j++
}
return res
}
|
单调栈
单调栈和单调队列类似，也是为了维持单调性，所以在插入的过程中需要删除一些元素。例如如果一个栈中暂时有数据{81，45，11，0}，那么要插入14的时候，就需要先把0,11出栈。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
type Monotonstack []int
func (m *Monotonstack) Push(x int) {
for len(*m) > 0 && (*m)[len(*m)-1] < x {
*m = (*m)[:len(*m)-1]
}
*m = append(*m, x)
}
// 之所以传入值 是因为可能需要取出的值已经不存在了
func (m *Monotonstack) Pop(x int) {
if x == (*m)[len(*m)-1] {
*m = (*m)[:len(*m)-1]
}
}
|
并查集
并查集是一种树形的数据结构，但是存储是使用数组进行存储的。主要用于处理一些不交集的合并及查询问题。
初始化
初始化就是初始化一个数组，并且本身在自己的集合之中。即fa[i]=i。
1
2
3
4
5
|
func makeSet(size int) {
for i:=0;i<size;i++ {
fa[i] = i
}
}
|
查找
通俗地讲一个故事：几个家族进行宴会，但是家族普遍长寿，所以人数众多。由于长时间的分离以及年龄的增长，这些人逐渐忘掉了自己的亲人，只记得自己的爸爸是谁了，而最长者（称为「祖先」）的父亲已经去世，他只知道自己是祖先。为了确定自己是哪个家族，他们想出了一个办法，只要问自己的爸爸是不是祖先，一层一层的向上问，直到问到祖先。如果要判断两人是否在同一家族，只要看两人的祖先是不是同一人就可以了。
1
2
3
4
5
6
7
|
func find(x int) int{
if fa[x] == x {
return x
}
return find(fa[x])
}
// 查找就是查找给定角色的祖先
|
路径压缩
如果只是需要查找祖先，则这样查找有较多的浪费，所以进行路径压缩，将路径上的各个节点都直接连接欸在根节点上。
1
2
3
4
5
6
|
func find(X int) int {
if fa[x] != x {
fa[x] = find(fa[x])
}
return fa[x]
}
|
合并
简单合并
两个不相交的并查集合并成为一个并查集，简单的合并就是让一个祖先成为另一个祖先的儿子。
1
2
3
4
5
|
func union(x, y int) {
x = find(x)
y = find(y)
fa[x] = y
}
|
按照秩合并
1
2
3
4
5
6
7
8
9
10
11
|
func union(x,y int) {
xx, yy := find(x), find(y)
if (xx == yy) {
return
}
if size[xx] > size[yy] {
xx, yy = yy, xx
}
fa[xx] = yy
size[yy] = size[xx] + size[yy]
}
|
引用
- 并查集 - OI Wiki (oi-wiki.org)