Alg | 栈/队列/排序

栈

包含 Min 函数的栈

问题

栈支持 $O(1)$ 入栈和出栈, 但不支持查询最小值

想法

直接：维护一个小顶堆 $O(logN)$
启示：用一个变量维护最小值，但如果最小值出栈后就不知道了 $\to$ 维护一个栈,来保存每时刻最小值

做法

建立两个栈，栈 A 存储原数据，栈 B 存储以栈底开头的每段数据的最小值
Push 时，A 中插入 x, B 中插入 $min(B 栈顶，x)$ ;
Pop 时，A,B 都需弹出栈顶;
GetMin 时，输出 B 的栈顶

Code

 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
29
30
31
32


var stk1,stk2 []int

func Push(x int) {
    stk1 = append(stk1, x)

    if len(stk2)==0{
        stk2 = append(stk2, x)
    }else{
        tmp := min(stk2[len(stk2)-1], x)
        stk2 = append(stk2, tmp)
    }
}

func Pop() {
    stk1 = stk1[:len(stk1)-1]
    stk2 = stk2[:len(stk2)-1]
}

func Top() int {
    return stk1[len(stk1)-1]
}

func Min() int {
    return stk2[len(stk2)-1]
}

func min(x, y int) int{
    if x>y{
        return y
    }
    return x
}

排序

第 K 大

问题

找出第 K 大的数 / 找出倒数第 K 大的（同一类问题）

想法

使用快排的思想 $O(nlogn)$
快排一轮 $\to$ 基准点左边比他大，右边比他小。或者相反。

实现

选取基准，将大的放到基准左边，小的放到右边
统计大于基准的数的个数 cnt
若 $k \leq cnt$ ,说明答案在左边，递归
若 $k>cnt$ ,说明答案在右边，递归

Code

 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
29
30
31
32
33
34
35
36
37


func findKth(q []int, n int, k int) int {
	return qsort(0, n-1, k, q)
}

func qsort(l, r, k int, q []int) int {
	if l == r {
		return q[l]
	}

	x := q[(l+r)>>1]
	i, j := l-1, r+1
	for i < j {
		for {
			i++
			if q[i] <= x {
				break
			}
		}

		for {
			j--
			if q[j] >= x {
				break
			}
		}

		if i < j {
			q[i], q[j] = q[j], q[i]
		}
	}

	sl := j - l + 1
	if k <= sl {
		return qsort(l, j, k, q)
	}
	return qsort(j+1, r, k-sl, q)
}