栈与队列

用栈实现队列

用两个栈实现先入先出队列

在Go中用切片模拟栈，一个输入栈，一个输出栈

入队：存入输入栈
出队：弹出输出栈顶，若输出栈为空，将输入栈所有数据存入输出栈

 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
38
39
40
41
42
43
44
45
46
47


type MyQueue struct {
    stackIn  []int // 输入栈
    stackOut []int // 输出栈
}

func Constructor() MyQueue {
    return MyQueue{
        stackIn:  make([]int, 0),
        stackOut: make([]int, 0),
    }
}

// 入队
func (this *MyQueue) Push(x int) {
    this.stackIn = append(this.stackIn, x) // 往输入栈追加
}

// 出队
func (this *MyQueue) Pop() int {
    if len(this.stackOut) == 0 { // 输出栈为空
        if len(this.stackIn) == 0 { // 输入栈也为空
            return -1
        }
        for i := len(this.stackIn) - 1; i >= 0; i-- { // 从输入栈顶逐个取元素存入输出栈
            this.stackOut = append(this.stackOut, this.stackIn[i]) // 输入栈元素存入输出栈
        }
        this.stackIn = []int{} // 清空输入栈
    }
    res := this.stackOut[len(this.stackOut)-1]           // 取出出栈元素
    this.stackOut = this.stackOut[:len(this.stackOut)-1] // 更新输出栈
    return res
}

// 获取队头值
func (this *MyQueue) Peek() int {
    res := this.Pop() // 出队
    if res == -1 {    // 队空
        return -1
    }
    this.stackOut = append(this.stackOut, res) // 放回输出栈
    return res
}

// 判队空
func (this *MyQueue) Empty() bool {
    return len(this.stackOut) == 0 && len(this.stackIn) == 0
}

时间复杂度: push和empty为O(1)，pop和peek为O(n)
空间复杂度: O(n)

用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

用两个队列实现一个后入先出（LIFO）的栈

其实这道题目就是用一个队列就够了，一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外）重新添加到队列尾部，此时再去弹出对头元素就是栈的顺序了

 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
38
39


type MyStack struct {
    queue []int
}

func Constructor() MyStack {
    return MyStack{
        queue: make([]int, 0),
    }
}

// 进栈
func (this *MyStack) Push(x int) {
    this.queue = append(this.queue, x) // 追加到队列尾
}

// 出栈
func (this *MyStack) Pop() int {
    // count:队首到倒数第二个元素的个数
    for count := len(this.queue) - 1; count != 0; count-- { // 除了最后一个元素其余元素重新加到队尾
        val := this.queue[0]                 // 取一个队首元素
        this.queue = this.queue[1:]          // 队首后面的元素前移
        this.queue = append(this.queue, val) // 重新加到队尾
    }
    res := this.queue[0]                       // 取队首元素
    this.queue = this.queue[1:len(this.queue)] // 更新队列
    return res
}

// 获取栈顶值
func (this *MyStack) Top() int {
    res := this.Pop()                    // 栈顶出栈
    this.queue = append(this.queue, res) // 重新加到队尾
    return res
}

// 判栈空
func (this *MyStack) Empty() bool {
    return len(this.queue) == 0
}

时间复杂度: pop为O(n)，其他为O(1)
空间复杂度: O(n)

有效的括号

20. 有效的括号 - 力扣（LeetCode）

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

遍历字符串，遇到左括号加入栈，遇到右括号就弹出栈顶元素（左括号），若不匹配，则返回false，遍历结束后，若栈内还剩左括号，返回false

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func isValid(s string) bool {
    stack := make([]rune, 0)
    for _, v := range s {
        if v == '(' || v == '[' || v == '{' { // 遍历到左括号
            stack = append(stack, v) // 入栈
        } else { // 遍历到右括号
            if len(stack) <= 0 { // 没有左括号
                return false
            }
            if v == ')' && stack[len(stack)-1] != '(' { // 左括号不匹配
                return false
            } else if v == ']' && stack[len(stack)-1] != '[' { // 左括号不匹配
                return false
            } else if v == '}' && stack[len(stack)-1] != '{' { // 左括号不匹配
                return false
            }
            stack = stack[:len(stack)-1] // 出栈
        }
    }
    if len(stack) > 0 { // 还剩左括号未匹配
        return false
    }
    return true
}

时间复杂度: O(n)
空间复杂度: O(n)

优化代码：哈希表，返回判断结果

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


func isValid(s string) bool {
    hash := map[rune]rune{')': '(', ']': '[', '}': '{'}
    stack := make([]rune, 0)
    for _, v := range s {
        if v == '(' || v == '[' || v == '{' { // 遍历到左括号
            stack = append(stack, v) // 入栈
        } else if len(stack) > 0 && stack[len(stack)-1] == hash[v] { // 遍历到右括号栈非空且匹配成功
            stack = stack[:len(stack)-1] // 出栈
        } else { // 遍历到右括号栈空或匹配不成功
            return false
        }
    }
    return len(stack) == 0
}

时间复杂度: O(n)
空间复杂度: O(n)

删除字符串中的所有相邻重复项

1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在 S 上反复执行重复项删除操作，直到无法继续删除。

遍历字符串，若栈为空或与栈顶元素不同，则入栈，若与栈顶元素不同，则栈顶元素出栈，遍历结束后，将栈中元素拼接为字符串返回

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


func removeDuplicates(s string) string {
    stack := make([]rune, 0)
    for _, v := range s {
        if len(stack) == 0 || stack[len(stack)-1] != v { // 栈为空或与栈顶元素不同
            stack = append(stack, v) // 入栈
        } else { // 栈非空且与栈顶元素相同
            stack = stack[:len(stack)-1] // 出栈
        }
    }
    return string(stack)
}

时间复杂度：O(n)
空间复杂度：O(n)

逆波兰表达式求值

150. 逆波兰表达式求值 - 力扣（LeetCode）

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

遍历给定字符串，遇到运算符就将栈顶两个元素取出用该运算符处理，结果再入栈，遍历结束返回栈中的运算结果

注意：除法中栈顶元素是除数

 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


func evalRPN(tokens []string) int {
    stack := make([]int, 0)
    for _, v := range tokens {
        if v == "+" { // 遍历到运算符
            val := stack[len(stack)-2] + stack[len(stack)-1] // 获取运算结果
            stack = stack[:len(stack)-1]                     // 更新栈
            stack[len(stack)-1] = val                        // 结果入栈
        } else if v == "-" { // 遍历到运算符
            val := stack[len(stack)-2] - stack[len(stack)-1] // 获取运算结果
            stack = stack[:len(stack)-1]                     // 更新栈
            stack[len(stack)-1] = val                        // 结果入栈
        } else if v == "*" { // 遍历到运算符
            val := stack[len(stack)-2] * stack[len(stack)-1] // 获取运算结果
            stack = stack[:len(stack)-1]                     // 更新栈
            stack[len(stack)-1] = val                        // 结果入栈
        } else if v == "/" { // 遍历到运算符
            val := stack[len(stack)-2] / stack[len(stack)-1] // 获取运算结果
            stack = stack[:len(stack)-1]                     // 更新栈
            stack[len(stack)-1] = val                        // 结果入栈
        } else { // 遇到数字
            val, _ := strconv.Atoi(v)
            stack = append(stack, val) // 入栈
        }
    }
    return stack[0]
}

时间复杂度：O(n)
空间复杂发：O(n)

压缩代码：swich

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func evalRPN(tokens []string) int {
    stack := make([]int, 0)
    for _, v := range tokens {
        val, err := strconv.Atoi(v) // 转为数字
        if err == nil {             // 说明是数字
            stack = append(stack, val) // 数字入栈
        } else { // 说明是运算符
            switch v {
                case "+": stack[len(stack)-2] = stack[len(stack)-2] + stack[len(stack)-1] // 运算结果入栈
                case "-": stack[len(stack)-2] = stack[len(stack)-2] - stack[len(stack)-1] // 运算结果入栈
                case "*": stack[len(stack)-2] = stack[len(stack)-2] * stack[len(stack)-1] // 运算结果入栈
                case "/": stack[len(stack)-2] = stack[len(stack)-2] / stack[len(stack)-1] // 运算结果入栈
            }
            stack = stack[:len(stack)-1] // 更新栈
        }
    }
    return stack[0]
}

时间复杂度：O(n)
空间复杂发：O(n)

滑动窗口最大值

239. 滑动窗口最大值 - 力扣（LeetCode）

给定一个数组和整数k，用k作为滑动窗口大小，窗口从最左侧移动到最右侧，每次移动一位，返回每次窗口移动后的最大值

单调队列：队首出队，队尾入队，队内元素单调；

pop(value)：若窗口移除的元素等于单调队列的队首元素，则队列弹出元素，否则不用任何操作
push(value)：若push的元素大于队尾元素，则弹出队尾元素，直到push的元素小于等于队尾元素或队空

保持如上规则，每次窗口移动的时候，只要取队首即可

 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54


type MyQueue struct {
    queue []int
}

func Constructor() *MyQueue {
    return &MyQueue{
        queue: make([]int, 0),
    }
}

// 获取队首元素
func (m *MyQueue) Front() int {
    return m.queue[0]
}

// 获取队尾元素
func (m *MyQueue) Back() int {
    return m.queue[len(m.queue)-1]
}

// 判队空
func (m *MyQueue) Empty() bool {
    return len(m.queue) == 0
}

// 入队
func (m *MyQueue) Push(val int) {
    for !m.Empty() && val > m.Back() { // 队非空且入队元素大于队尾元素
        m.queue = m.queue[:len(m.queue)-1] // 弹出队尾元素
    }
    m.queue = append(m.queue, val) // 入队尾
}

// 出队
func (m *MyQueue) Pop(val int) {
    if !m.Empty() && val == m.Front() { // 队非空且出队元素等于队首元素
        m.queue = m.queue[1:] // 队首出队
    }
}

func maxSlidingWindow(nums []int, k int) []int {
    queue := Constructor()
    res := make([]int, 0)
    for i := 0; i < k; i++ { // 前k个元素入队
        queue.Push(nums[i]) // 入队
    }
    res = append(res, queue.Front()) // 记录前k个元素的最大值
    for i := k; i < len(nums); i++ { // 遍历数组   
        queue.Pop(nums[i-k]) // 滑动窗口移除最前面的元素
        queue.Push(nums[i]) // 滑动窗口添加最后面的元素
        res = append(res, queue.Front()) // 记录最大值
    }
    return res
}

时间复杂度: O(n)
空间复杂度: O(k)

前 K 个高频元素

347. 前 K 个高频元素 - 力扣（LeetCode）

给定一个数组和一个整数 k ，返回数组中出现频率前 k 高的元素

先统计频率，再对频率排序；统计元素出现的频率可以用map；对频率进行排序，可以用快排和堆

快排

用map统计完频率后，收集不重复的元素，利用字典值对不重复的元素排序，最后返回前k个不重复的元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


func topKFrequent(nums []int, k int) []int {
    res := make([]int, 0)
    mp := make(map[int]int)
    for _, v := range nums { // 遍历数组
        mp[v]++ // 字典值(频率)加一
    }
    for key := range mp { // 遍历字典key
        res = append(res, key) // 记录不重复的元素
    }
    sort.Slice(res, func(a, b int) bool {
        return mp[res[a]] > mp[res[b]] // 降序
    })
    return res[:k]
}

时间复杂度: O(nlogn)
空间复杂度: O(n)

用map统计完频率后，构建小顶堆

堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。如果是父结点大于等于左右孩子那就是大顶堆，小于等于左右孩子就是小顶堆。大顶堆（堆头是最大元素），小顶堆（堆头是最小元素），用小顶堆每次将最小的元素弹出，最后小顶堆里积累的就是前k个最大元素

更深理解

之所以将交换、比较等操作分离出来，是因为增删切片元素需要传递切片地址，操作切片指针时，无法用索引下标访问数组元素
Go语言中函数参数的传递方式都是值传递

 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97


type Heap [][2]int // 二维表示元素及其频率

// 交换两个节点 
func (h Heap) swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

// 比较两个节点
func (h Heap) less(i, j int) bool {
    return h[i][1] < h[j][1] // 比较频率 如果实现的是大顶堆，修改这里的判断即可
}

// 节点向上比较交换
func (h Heap) up(i int) {
    for {
        f := (i - 1) / 2            // 父节点在数组中的位置
        if i == f || h.less(f, i) { // 当前节点为根节点或父节点小于当前节点
            break
        }
        h.swap(f, i) // 交换当前节点和父节点的值
        i = f        // 更新当前节点索引继续向上比较
    }
}

// 注意go中所有参数都是值传递 所以要让h的变化在函数外也起作用 此处要传指针
// 添加节点
func (h *Heap) Push(x [2]int) {
    *h = append(*h, x) // 加入末尾
    h.up(len(*h) - 1)  // 向上比较交换
}

// 节点向下比较交换
func (h Heap) down(i int) {
    for {
        l := 2*i + 1     // 左孩子
        r := 2*i + 2     // 右孩子
        if l >= len(h) { // 当前节点已经是叶子节点
            break
        }
        minChild := l                   // 默认左孩子值小于右孩子值
        if r < len(h) && h.less(r, l) { // 右孩子存在且小于左孩子
            minChild = r // 更新当前节点的最小子节点
        }
        if h.less(i, minChild) { // 当前节点小于最小子节点
            break
        }
        h.swap(i, minChild) // 交换当前节点和最小子节点位置
        i = minChild        // 更新当前节点索引继续向下比较
    }
}

// 删除堆中位置为i的节点 返回被删节点的值
func (h *Heap) Remove(i int) ([2]int, bool) {
    if i < 0 || i > len(*h)-1 { // 索引越界
        return [2]int{0, 0}, false
    }
    n := len(*h) - 1 // 最后一个节点的索引
    h.swap(i, n)     // 交换要被删除节点和最后的节点
    x := (*h)[n]     // 保存最后节点值
    *h = (*h)[0:n]   // 删除最后节点
    h.down(i)        // 被交换的当前节点向下比较交换
    return x, true
}

// 弹出堆顶的元素，并返回其值
func (h *Heap) Pop() [2]int {
    x, _ := h.Remove(0)
    return x
}

// 根据传入的切片建堆
func BuildHeap(arr [][2]int) Heap {
    h := Heap(arr)                       // 获取给定切片
    for i := len(h)/2 - 1; i >= 0; i-- { // 从堆中末尾节点的父节点到根节点
        h.down(i) // 向下比较交换
    }
    return h
}

func topKFrequent(nums []int, k int) []int {
    mp := map[int]int{}
    res := make([]int, 0)
    for _, v := range nums { // 遍历数组
        mp[v]++ // 字典值(频率)加一
    }
    h := BuildHeap([][2]int{})   // 初始化堆
    for key, value := range mp { // 遍历字典
        h.Push([2]int{key, value}) // 元素入堆
        if len(h) > k {            // 堆的节点数超过k个
            h.Pop() // 删除顶点(min)
        }
    }
    for i := 0; i < k; i++ { // 遍历堆
        res = append(res, h.Pop()[0])
    }
    return res
}

时间复杂度: O(nlogk)
空间复杂度: O(n)

使用go中标准库提供的heap，需要先实现两个接口定义的五个方法：

 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
38
39
40
41
42
43
44
45
46
47
48
49
50


type Heap [][2]int // 二维表示元素及其频率

func (h Heap) Len() int {
    return len(h)
}

// 比较两个节点
func (h Heap) Less(i, j int) bool {
    return h[i][1] < h[j][1] // 按照频率排序节点
}

// 交换两个节点
func (h Heap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

// go中所有参数都是值传递 所以要让h的变化在函数外也起作用 此处要传指针
// 添加节点
func (h *Heap) Push(x interface{}) {
    *h = append(*h, x.([2]int)) // 向末尾添加节点
}

// 删除节点
func (h *Heap) Pop() interface{} {
    old := *h         // 保存当前根
    n := len(old)     // 节点数
    x := old[n-1]     // 保存最后一个节点
    *h = old[0 : n-1] // 删除最后一个节点
    return x          // 返回删除的节点
}

func topKFrequent(nums []int, k int) []int {
    mp := map[int]int{}
    res := make([]int, k)
    for _, v := range nums { // 遍历数组
        mp[v]++ // 字典值(频率)加一
    }
    h := &Heap{}                 // 初始化堆
    heap.Init(h)                 // 用go标准库提供的heap
    for key, value := range mp { // 遍历字典
        heap.Push(h, [2]int{key, value}) // 元素入堆
        if h.Len() > k {                 // 堆的节点数超过k个
            heap.Pop(h) // 删除顶点(min)
        }
    }
    for i := 0; i < k; i++ { // 遍历堆
        res[k-i-1] = heap.Pop(h).([2]int)[0] // 将堆中排序后的元素加入结果集
    }
    return res
}

自己实现小顶堆

借助 哈希表 来建立数字和其出现次数的映射，遍历一遍数组统计元素的频率
维护一个元素数目为 k 的最小堆
每次都将新的元素与堆顶元素（堆中频率最小的元素）进行比较
如果新的元素的频率比堆顶端的元素大，则弹出堆顶端的元素，将新的元素添加进堆中
最终，堆中的 k 个元素即为前 k 个高频元素

 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64


func topKFrequent(nums []int, k int) []int {
    res := make([]int, 0)
    // 统计各元素频率
    mp := make(map[int]int)
    for _, v := range nums {
        mp[v]++
    }
    // 维护一个大小为k的最小堆
    // 每个节点表示为元素及其频率
    heap := make([][2]int, 0)
    // 遍历字典元素入堆
    for key, v := range mp {
        // 判当前堆大小是否大于k
        if len(heap) >= k {
            // 判当前元素是否小于堆顶元素
            if v < heap[0][1] {
                // 当前元素无需入堆
                continue
            } else {
                // 修改堆顶元素为当前元素
                heap[0] = [2]int{key, v}
            }
        } else {
            // 当前元素入堆
            heap = append(heap, [2]int{key, v})
        }
        // 堆化,从尾节点遍历到根节点,维护小顶堆性质
        for i := len(heap)/2 - 1; i >= 0; i-- {
            heapify(heap, len(heap), i)
        }
    }
    // 小顶堆排序为降序
    for i := len(heap) - 1; i >= 0; i-- {
        // 交换堆顶元素和未排定的末尾元素
        heap[0], heap[i] = heap[i], heap[0]
        // 将未排定元素从堆顶向下重新堆化
        heapify(heap, i, 0)
    }
    // 将堆中元素全部放入结果集
    for _, v := range heap {
        res = append(res, v[0])
    }
    return res
}
func heapify(heap [][2]int, len, curIdx int) {
    // 初始化最小元素索引为当前元素索引
    minIdx := curIdx
    // 求得当前元素左右孩子索引
    l := 2*curIdx + 1
    r := 2*curIdx + 2
    // 判左右孩子是否小于当前最小元素
    if l < len && heap[l][1] < heap[minIdx][1] {
        minIdx = l
    }
    if r < len && heap[r][1] < heap[minIdx][1] {
        minIdx = r
    }
    if minIdx != curIdx {
        // 交换当前元素与最小元素
        heap[curIdx], heap[minIdx] = heap[minIdx], heap[curIdx]
        // 向下递归
        heapify(heap, len, minIdx)
    }
}

桶排序

依旧使用哈希表统计频率，统计完成后，创建一个数组，将频率作为数组下标，对于出现频率不同的数字集合，存入对应的数组下标即可

由于k不会大于数组长度且最大频率可能为len(nums)，所以定义len(nums)+1个桶，每个桶中存相同频率的元素

 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
38
39


func topKFrequent(nums []int, k int) []int {
    res := make([]int, 0)
    // 统计各元素频率
    mp := make(map[int]int)
    for _, v := range nums {
        mp[v]++
    }
    // 初始化len(nums)+1个桶
    // 每个桶中存相同频率的元素
    buckets := make([][]int, len(nums)+1)
    // 遍历字典元素入对应桶
    for key, v := range mp {
        // 判该频率的桶是否为空
        if len(buckets[v]) == 0 {
            // 初始化该频率的桶
            buckets[v] = make([]int, 0)
        }
        // 按频率将元素放入对应桶
        buckets[v] = append(buckets[v], key)
    }
    // 倒序遍历桶取k个元素
    for i := len(buckets) - 1; i >= 0; i-- {
        // 判该桶是否非空
        if len(buckets[i]) != 0 {
            // 遍历该桶
            for _, v := range buckets[i] {
                // 桶中当前元素加入结果集
                res = append(res, v)
                // 更新k
                k--
                // 判是否取够k个元素
                if k == 0 {
                    return res
                }
            }
        }
    }
    return res
}

附加

最小栈

155. 最小栈 - 力扣（LeetCode）

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈

思路一：维护一个整型量保存最小值，在push和pop时更新最小值属性，若pop了最小值，则要遍历栈更新最小值（不推荐）

 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


type MinStack struct {
    minVal int
    stack  []int
}

func Constructor() MinStack {
    return MinStack{
        minVal: math.MaxInt, 
        stack: make([]int, 0)}
}

func (this *MinStack) Push(val int) {
    this.stack = append(this.stack, val)
    if val < this.minVal {
        this.minVal = val
    }
}

func (this *MinStack) Pop() {
    if this.Top() == this.minVal {
        this.minVal = math.MaxInt
        for i := 0; i < len(this.stack)-1; i++ {
            if this.stack[i] < this.minVal {
                this.minVal = this.stack[i]
            }
        }
    }
    this.stack = this.stack[:len(this.stack)-1]
}

func (this *MinStack) Top() int {
    return this.stack[len(this.stack)-1]
}

func (this *MinStack) GetMin() int {
    return this.minVal
}

思路二：维护一个最小栈，保证栈顶一定是最小值，若push元素大于最小值，则向最小栈push最小值，pop正常。保证每次pushpop后最小栈顶一定最小

 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


type MinStack struct {
    min   []int
    stack []int
}

func Constructor() MinStack {
    return MinStack{
        min:   make([]int, 0),
        stack: make([]int, 0)}
}

func (this *MinStack) Push(val int) {
    minVal := this.GetMin()
    if val < minVal {
        this.min = append(this.min, val)
    } else {
        this.min = append(this.min, minVal)
    }
    this.stack = append(this.stack, val)
}

func (this *MinStack) Pop() {
    this.min = this.min[:len(this.min)-1]
    this.stack = this.stack[:len(this.stack)-1]
}

func (this *MinStack) Top() int {
    return this.stack[len(this.stack)-1]
}

func (this *MinStack) GetMin() int {
    if len(this.min) != 0 {
        return this.min[len(this.min)-1]
    }
    return 1 << 31 // 最小整型值
}

字符串解码

394. 字符串解码 - 力扣（LeetCode）

给定一个字符串，将括号里的字符重复括号前数字的次数，最终返回一个字符串

思路：遍历字符串入栈，遇到右括号时，不断弹栈，保存括号里的字符和括号前的数字，将括号里字符重复入栈给定次数

 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72


func decodeString(s string) string {
    stack := make([]rune, 0)
    for _, v := range s {
        // 解码
        if v == ']' {
            temp := make([]rune, 0)
            // 逆序取出括号中的字符串
            for stack[len(stack)-1] != '[' {
                temp = append(temp, stack[len(stack)-1])
                stack = stack[:len(stack)-1]
            }
            // 弹出'['
            stack = stack[:len(stack)-1]
            // 保存重复次数(rune -> int)
            countSlice := make([]rune, 0)
            // 逆序取出数字
            for len(stack) != 0 && stack[len(stack)-1] <= '9' && stack[len(stack)-1] >= '0' {
                countSlice = append(countSlice, stack[len(stack)-1])
                stack = stack[:len(stack)-1]
            }
            // 翻转
            for i, j := 0, len(countSlice)-1; i < j; i, j = i+1, j-1 {
                countSlice[i], countSlice[j] = countSlice[j], countSlice[i]
            }
            count, _ := strconv.Atoi(string(countSlice))
            // 重复字符入栈
            for range count {
                // 逆序遍历括号中字符
                for i := len(temp) - 1; i >= 0; i-- {
                    stack = append(stack, temp[i])
                }
            }
        } else {
            stack = append(stack, v)
        }
    }
    return string(stack)
}
// 写法二：用slices.Reverse翻转 直接追加打散的切片元素
func decodeString(s string) string {
    stack := make([]byte, 0)
    for i := 0; i < len(s); i++ {
        if s[i] == ']' {
            // 取出逆序字符串
            inter := make([]byte, 0)
            for len(stack) != 0 && stack[len(stack)-1] != '[' {
                inter = append(inter, stack[len(stack)-1])
                stack = stack[:len(stack)-1]

            }
            // 弹出]
            stack = stack[:len(stack)-1]
            // 取出逆序数字
            countByte := make([]byte, 0)
            for len(stack) != 0 && stack[len(stack)-1] >= '0' && stack[len(stack)-1] <= '9' {
                countByte = append(countByte, stack[len(stack)-1])
                stack = stack[:len(stack)-1]
            }
            // 翻转逆序
            slices.Reverse(countByte)
            slices.Reverse(inter)
            count, _ := strconv.Atoi(string(countByte))
            // 解码字符串入栈
            for j := 0; j < count; j++ {
                stack = append(stack, inter...)
            }
        } else {
            stack = append(stack, s[i])
        }
    }
    return string(stack)
}

克隆图

133. 克隆图 - 力扣（LeetCode）

给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）

思路一：非递归，用栈实现（不推荐）

 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58


func cloneGraph(node *Node) *Node {
    if node == nil {
        return node
    }
    stack := make([]*Node, 0)
    newStack := make([]*Node, 0)
    mp := make(map[int]*Node)
    temp := make(map[int]bool)
    // 给定节点入栈
    stack = append(stack, node)
    temp[node.Val] = true
    // 遍历所有旧节点创建对应新节点
    for len(stack) != 0 {
        // 取出一个节点作为当前节点
        cur := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        // 将当前节点的邻居节点入栈
        for _, v := range cur.Neighbors {
            // 未遍历过该节点
            if !temp[v.Val] {
                stack = append(stack, v)
                temp[v.Val] = true
            }
        }
        // 构造当前节点的拷贝
        newNode := &Node{
            Val:       cur.Val,
            Neighbors: cur.Neighbors,
        }
        // 将新节点存入字典
        mp[newNode.Val] = newNode
        // 将新节点存入新栈
        newStack = append(newStack, newNode)
    }
    for len(newStack) != 0 {
        // 取出一个节点作为当前节点
        cur := newStack[len(newStack)-1]
        newStack = newStack[:len(newStack)-1]
        // 保存当前节点的新邻居节点
        temp := make([]*Node, 0)
        // 遍历当前节点的邻居节点
        for i := 0; i < len(cur.Neighbors); i++ {
            // 在字典中找到对应的新节点
            if v, ok := mp[cur.Neighbors[i].Val]; ok {
                // 保存当前节点的新邻居节点
                temp = append(temp, v)
            }
        }
        // 修改所有邻居节点为新节点
        cur.Neighbors = nil
        cur.Neighbors = append(cur.Neighbors, temp...)
    }
    // 字典中找给定节点对应的新节点
    if v, ok := mp[node.Val]; ok {
        return v
    }
    return nil
}

思路二：递归

 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


func cloneGraph(node *Node) *Node {
    // 记录旧->新节点的对应
    mp := make(map[*Node]*Node)
    return clone(node, mp)
}
func clone(cur *Node, mp map[*Node]*Node) *Node {
    if cur == nil {
        return cur
    }
    // 字典中存在该节点对应的新节点
    if v, ok := mp[cur]; ok {
        return v
    }
    // 构建新节点
    newNode := &Node{
        Val: cur.Val,
        Neighbors: make([]*Node, len(cur.Neighbors)),
    }
    // 更新字典:旧节点->新节点
    mp[cur] = newNode
    // 遍历当前节点的邻居节点
    for i := 0; i < len(cur.Neighbors); i++ {
        newNode.Neighbors[i] = clone(cur.Neighbors[i], mp)
    }
    return newNode
}

01 矩阵

542. 01 矩阵 - 力扣（LeetCode）

思路一：对每个元素BFS（超时）

 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58


func updateMatrix(mat [][]int) [][]int {
    // 遍历给定矩阵
    for i := 0; i < len(mat); i++ {
        for j := 0; j < len(mat[0]); j++ {
            // 遇到元素1
            if mat[i][j] == 1 {
                queue := make([][2]int, 0)
                // 当前元素入队
                queue = append(queue, [2]int{i, j})
                // 记录距离
                dist := 0
                // 标记是否找到最近元素0
                isFind := false
                // 标记该坐标是否被遍历过
                mp := make(map[[2]int]bool)
                // BFS
                for len(queue) != 0 && !isFind {
                    // 记录本层元素数
                    count := len(queue)
                    // 遍历本层所有元素
                    for k := 0; k < count && !isFind; k++ {
                        // 记录队首元素后出队
                        curI, curJ := queue[0][0], queue[0][1]
                        queue = queue[1:]
                        // 标记当前元素已遍历过
                        mp[[2]int{curI, curJ}] = true
                        // 找到元素0
                        if mat[curI][curJ] == 0 {
                            // 修改矩阵对应元素为距离
                            mat[i][j] = dist
                            // 标记找到最近元素0
                            isFind = true
                        }
                        // 上方元素入队
                        if curI != 0 && !mp[[2]int{curI - 1, curJ}] {
                            queue = append(queue, [2]int{curI - 1, curJ})
                        }
                        // 下方元素入队
                        if curI != len(mat)-1 && !mp[[2]int{curI + 1, curJ}] {
                            queue = append(queue, [2]int{curI + 1, curJ})
                        }
                        // 左方元素入队
                        if curJ != 0 && !mp[[2]int{curI, curJ - 1}] {
                            queue = append(queue, [2]int{curI, curJ - 1})
                        }
                        // 右方元素入队
                        if curJ != len(mat[0])-1 && !mp[[2]int{curI, curJ + 1}] {
                            queue = append(queue, [2]int{curI, curJ + 1})
                        }
                    }
                    // 距离+1
                    dist++
                }
            }
        }
    }
    return mat
}

思路二BFS：更新每个元素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
28
29
30
31
32
33
34
35
36
37
38


func updateMatrix(mat [][]int) [][]int {
    queue := make([][2]int, 0)
    // 遍历给定矩阵
    for i := 0; i < len(mat); i++ {
        for j := 0; j < len(mat[0]); j++ {
            // 遇到元素0
            if mat[i][j] == 0 {
                // 坐标入队
                queue = append(queue, [2]int{i, j})
            } else {
                // 标记当前元素需要更新
                mat[i][j] = -1
            }
        }
    }
    // 设置四周偏移量
    ds := [4][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    // 遍历队列
    for len(queue) != 0 {
        // 保存队首后出队
        x, y := queue[0][0], queue[0][1]
        queue = queue[1:]
        // 遍历当前元素的四周
        for _, offset := range ds {
            // 给当前元素下标设置偏移量
            curX := x + offset[0]
            curY := y + offset[1]
            // 坐标有效且对应元素需要更新
            if curX >= 0 && curY >= 0 && curX < len(mat) && curY < len(mat[0]) && mat[curX][curY] == -1 {
                // 更新元素值
                mat[curX][curY] = mat[x][y] + 1
                // 更新后元素的下标入队
                queue = append(queue, [2]int{curX, curY})
            }
        }
    }
    return mat
}

时间复杂度: O(n)
空间复杂度: O(n)

数据流的中位数

295. 数据流的中位数 - 力扣（LeetCode）

使用两个优先队列（堆）来维护整个数据流数据，为了可以在 O(1) 的复杂度内取得当前中位数，令 l 为大根堆，r 为小根堆，并人为固定 l 和 r 之前存在如下关系：

当数据流元素数量为偶数：l 和 r 大小相同，此时中位数为两者堆顶元素的平均值；
当数据流元素数量为奇数：l 比 r 多一，此时中位数为 l 的堆顶原数

当添加一个数 num 时需要分情况讨论：

$num≤max{l}$

此时 num 小于等于中位数，需要将该数添加到 l 中。新的中位数将小于等于原来的中位数，因此可能需要将 l 中最大的数移动到 r 中。
$num>max{r}$

此时 num 大于中位数，需要将该数添加到 r 中。新的中位数将大于等于原来的中位数，因此可能需要将 r 中最小的数移动到 l 中。

具体是否移动取决与俩堆的大小，目标是维持俩堆大小相等或左比右大1

特别地，当 l 为空时，将 num 添加到 l 中

  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
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109


type MedianFinder struct {
    heapL Heap // 大顶堆
    heapR Heap // 小顶堆
}

func Constructor() MedianFinder {
    return MedianFinder{
        heapL: Heap{},
        heapR: Heap{},
    }
}

func (this *MedianFinder) AddNum(num int) {
    // 判大顶堆是否为空或加入值小于大顶堆顶
    if len(this.heapL) == 0 || num < this.heapL[0] {
        // 加入大顶堆
        this.heapL.Push(num, 1)
        // 判大顶堆元素是否比小顶堆元素多一个以上
        if len(this.heapL)-len(this.heapR) > 1 {
            // 大顶堆顶移至小顶堆
            this.heapR.Push(this.heapL.Pop(1), 0)
        }
    } else {
        // 加入小顶堆
        this.heapR.Push(num, 0)
        // 判小顶堆元素是否多于大顶堆
        if len(this.heapR) > len(this.heapL) {
            // 小顶堆顶移至大顶堆
            this.heapL.Push(this.heapR.Pop(0), 1)
        }
    }
}

func (this *MedianFinder) FindMedian() float64 {
    // 判大顶堆元素是否多于小顶堆
    if len(this.heapL) > len(this.heapR) {
        return float64(this.heapL[0])
    } else {
        return float64(this.heapL[0]+this.heapR[0]) / 2.0
    }
}

type Heap []int

func (h Heap) swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h Heap) less(i, j, sign int) bool {
    if sign == 0 {
        // 小顶堆
        return h[i] < h[j]
    } else {
        // 大顶堆
        return h[i] > h[j]
    }
}

func (h Heap) up(i, sign int) {
    father := (i - 1) / 2
    if father >= 0 && h.less(i, father, sign) {
        h.swap(father, i)
        h.up(father, sign)
    }
}

func (h Heap) down(i, sign int) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2
    if left < len(h) && h.less(left, largest, sign) {
        largest = left
    }
    if right < len(h) && h.less(right, largest, sign) {
        largest = right
    }
    if largest != i {
        h.swap(largest, i)
        h.down(largest, sign)
    }
}

func (h *Heap) Push(x, sign int) {
    *h = append(*h, x)
    h.up(len(*h)-1, sign)
}

func (h *Heap) Remove(i, sign int) (int, bool) {
    if i < 0 || i >= len(*h) {
        return -1, false
    }
    h.swap(i, len(*h)-1)
    x := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    if i < len(*h) {
        father := (i - 1) / 2
        if father >= 0 && h.less(i, father, sign) {
            h.up(i, sign)
        } else {
            h.down(i, sign)
        }
    }
    return x, true
}

func (h *Heap) Pop(sign int) int {
    x, _ := h.Remove(0, sign)
    return x
}

时间复杂度：
- addNum: O(logn)，其中 n 为累计添加的数的数量
- findMedian: O(1)。
空间复杂度：O(n)，主要为堆的开销

简化路径

71. 简化路径 - 力扣（LeetCode）

给定一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），要求将其转化为 更加简洁的规范路径。

在 Unix 风格的文件系统中规则如下：

一个点 '.' 表示当前目录本身。
此外，两个点 '..' 表示将目录切换到上一级（指向父目录）。
任意多个连续的斜杠（即，'//' 或 '///'）都被视为单个斜杠 '/'。
任何其他格式的点（例如，'...' 或 '....'）均被视为有效的文件/目录名称。

返回的 简化路径 必须遵循下述格式：

始终以斜杠 '/' 开头。
两个目录名之间必须只有一个斜杠 '/' 。
最后一个目录名（如果存在）不能以 '/' 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的 规范路径

思路：栈内只存有效文件/目录名，最后对栈内各元素加分隔符

 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65


// 写法一：手动分割
func simplifyPath(path string) string {
    // 栈内存各个有效文件/目录名称
    stack := make([]string, 0)
    i := 0
    for i < len(path) {
        // 判是否遇到.
        if path[i] == '.' {
            // 遍历该连续.
            cnt := 0
            for i < len(path) && path[i] == '.' {
                i++
                cnt++
            } // 此时i指向不为.
            // 判是否为.开头的文件/目录名称
            if i < len(path) && path[i] != '/' {
                start := i
                // 遍历该有效字符
                for i < len(path) && path[i] != '/' {
                    i++
                } // 此时i指向/
                stack = append(stack, path[start-cnt:i])
            } else if cnt == 1 { // 处理.
                continue
            } else if len(stack) != 0 && cnt == 2 {
                stack = stack[:len(stack)-1]
            } else if cnt >= 3 {
                stack = append(stack, path[i-cnt:i])
            }
        } else if path[i] == '/' {
            for i < len(path) && path[i] == '/' {
                i++
            } // 此时i指向不为/
        } else { // 此时i指向有效字符且非.
            start := i
            // 遍历该有效字符
            for i < len(path) && path[i] != '/' {
                i++
            } // 此时i指向/
            stack = append(stack, path[start:i])
        }
    }
    // 将各有效文件/目录用分隔符'/'连接
    res := strings.Join(stack, "/")
    // 路径首加/
    res = "/" + res
    return res
}
// 写法二：调库函数分割
func simplifyPath(path string) string {
    // 栈内存储有效文件/目录名称
    stack := []string{}
    // 遍历按分隔符'/'切割后的字符串切片
    for _, v := range strings.Split(path, "/") {
        if v == ".." {
            if len(stack) != 0 {
                stack = stack[:len(stack)-1]
            }
        } else if v != "." && v != "" {
            stack = append(stack, v)
        }
    }
    res := "/" + strings.Join(stack, "/")
    return res
}

时间复杂度：O(n)
空间复杂度：O(n)

基本计算器

224. 基本计算器 - 力扣（LeetCode）

给定一个字符串表达式 s ，实现一个基本计算器来计算并返回它的值。

思路：使用两个栈 nums 和 ops

nums ：存放所有的数字
ops ：存放加、减、左括号

从前往后对遍历到的字符分情况处理：

空格 : 跳过
( : 直接加入 ops 中，等待与之匹配的 )
数字 : 从当前位置开始继续往后取，将整一个连续数字整体取出，加入 nums
) : 使用现有的 nums 和 ops 进行计算，直到ops为空或遇到左括号，计算结果放到 nums，ops中该左括号出栈
+/- : 使用现有的 nums 和 ops 进行计算，直到ops为空或遇到左括号，计算结果放到 nums，最后+/-入栈，；若为(-，则加0后再入栈

注意：

由于第一个数可能是负数，为了减少边界判断。一个小技巧是先往 nums 添加一个 0
为防止 () 内出现的首个字符为运算符，将所有的空格去掉，并将 (- 替换为 (0-，(+ 替换为 (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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53


func calculate(s string) int {
    // 清除字符串s中所有空格
    s = strings.ReplaceAll(s, " ", "")
    // nums中预加0防止一开始为-
    nums, ops := []int{0}, []byte{}
    // 利用nums和ops计算
    cal := func() {
        op := ops[len(ops)-1]
        ops = ops[:len(ops)-1]
        if op == '+' {
            nums[len(nums)-2] += nums[len(nums)-1]
        } else {
            nums[len(nums)-2] -= nums[len(nums)-1]
        }
        nums = nums[:len(nums)-1]
    }
    for i := 0; i < len(s); i++ {
        if s[i] == ' ' {
            continue
        } else if s[i] == '(' {
            ops = append(ops, '(')
        } else if s[i] <= '9' && s[i] >= '0' {
            // 将整一个连续数字整体取出
            start := i
            for i < len(s) && s[i] >= '0' && s[i] <= '9' {
                i++
            }
            num, _ := strconv.Atoi(s[start:i])
            nums = append(nums, num)
            i--
        } else { // + - )
            // 处理ops中+/-
            for len(ops) != 0 && ops[len(ops)-1] != '(' {
                cal()
            }
            if s[i] == ')' {
                // (出栈
                ops = ops[:len(ops)-1]
            } else { // +/-
                // 判字符串中是否为(-或(+
                if i != 0 && s[i-1] == '(' {
                    // 加0变(0-或(0+
                    nums = append(nums, 0)
                }
                ops = append(ops, s[i])
            }
        }
    }
    if len(ops) != 0 {
        cal()
    }
    return nums[len(nums)-1]
}

时间复杂度：O(n)
空间复杂度：O(n)

从字符串中移除星号

2390. 从字符串中移除星号 - 力扣（LeetCode）

给定一个包含若干星号 * 的字符串 s 。移除星号及其左侧最近的那个非星号字符，返回移除所有星号之后的字符串

思路：栈

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


func removeStars(s string) string {
    stack := make([]byte, 0)
    for _, ch := range s {
        if ch == '*' {
            stack = stack[:len(stack)-1]
        } else {
            stack = append(stack, byte(ch))
        }
    }
    return string(stack)
}

小行星碰撞

735. 小行星碰撞 - 力扣（LeetCode）

给定一个整数数组 asteroids，表示在同一行的小行星。

对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。

找出碰撞后剩下的所有小行星。碰撞规则：两个小行星相互碰撞，较小的小行星会爆炸。如果两颗小行星大小相同，则两颗小行星都会爆炸。两颗移动方向相同的小行星，永远不会发生碰撞。

思路：栈

注意：只有当前元素为负（向左）与栈顶元素为正（向右）才会碰撞，当前元素为正（向右）栈顶元素为负（向左）不会碰撞

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func asteroidCollision(asteroids []int) []int {
    stack := make([]int, 0)
    for _, cur := range asteroids {
        // 标记当前元素是否存在
        curAlive := true
        // 不断循环直至当前元素爆炸或栈空或当前元素与栈顶不碰撞
        for curAlive && len(stack) != 0 && cur < 0 && stack[len(stack)-1] > 0 {
            // 判当前元素是否存在
            curAlive = -cur > stack[len(stack)-1]
            // 判栈顶元素是否爆炸
            if stack[len(stack)-1] <= -cur {
                stack = stack[:len(stack)-1]
            }
        }
        if curAlive {
            stack = append(stack, cur)
        }
    }
    return stack
}

Dota2 参议院

给定一个字符串，其中只包含R和D两种字符，分别代表两个阵营的参议院，每轮中每个议员可以禁止另一议员的权利或宣布胜利，失去权利的议员将在过程中被跳过，若议员发现有权利投票的议员都是 同一个阵营的 ，则可以该阵营宣布胜利，返回胜利的阵营输出，应该是 "Radiant" 或 "Dire"

思路：贪心 + 循环队列

创建两个队列，遍历一遍字符串，按照投票顺序（下标）分别存储R方和D方每一名议员（下标）
逐个比较队首，值小的说明先投，另一个队首出队（ban），值小的从队首出队加上字符串长度后（代表是下一轮）加入队尾
当一方队列为空，另一方获胜

注意：值小的从队首出队加上字符串长度，可以保证这个议员只会参加下一轮，或者被上一轮的对手干掉

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func predictPartyVictory(senate string) string {
    rQueue, dQueue := []int{}, []int{}
    for i, ch := range senate {
        if ch == 'R' {
            rQueue = append(rQueue, i)
        } else {
            dQueue = append(dQueue, i)
        }
    }
    for len(rQueue) != 0 && len(dQueue) != 0 {
        if rQueue[0] < dQueue[0] {
            rQueue = append(rQueue, rQueue[0]+len(senate))
        } else {
            dQueue = append(dQueue, dQueue[0]+len(senate))
        }
        rQueue = rQueue[1:]
        dQueue = dQueue[1:]
    }
    if len(rQueue) == 0 {
        return "Dire"
    }
    return "Radiant"
}

无限集中的最小数字

2336. 无限集中的最小数字 - 力扣（LeetCode）

现有一个包含所有正整数的集合 [1, 2, 3, 4, 5, ...] 。

实现 SmallestInfiniteSet 类：

SmallestInfiniteSet() 初始化 SmallestInfiniteSet 对象以包含所有正整数。
int popSmallest() 移除并返回该无限集中的最小整数。
void addBack(int num) 如果正整数 num 不存在于无限集中，则将一个 num 添加到该无限集中

思路：小顶堆

优化：用一个 idx 变量代表顺序弹出的集合左边界，[idx,+∞] 范围内的数均为待弹出，起始有 idx=1。

考虑当调用 addBack 往集合添加数值 x 时，该如何处理：

x ≥ idx：说明数值本身就存在于集合中，忽略该添加操作；
x = idx−1：数值刚好位于边界左侧，更新 idx=idx−1；
x < idx−1：考虑将数值添加到某个容器中，该容器支持返回最小值，容易联想到“小根堆”；但小根堆并没有“去重”功能，为防止重复弹出，还需额外使用“哈希表”来记录哪些元素在堆中。

该做法本质上将集合分成两类，一类是从 idx 到正无穷的连续段，对此类操作的复杂度为 O(1)；一类是比 idx 要小的离散类数集，对该类操作复杂度为 O(logn)，其中 n 为调用 addBack 的最大次数

  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
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114


// 写法一
type Heap []int
type SmallestInfiniteSet struct {
    heap Heap
    mp   map[int]bool
}

func Constructor() SmallestInfiniteSet {
    smallestInfiniteSet := SmallestInfiniteSet{}
    smallestInfiniteSet.mp = map[int]bool{}
    for i := 1; i <= 1000; i++ {
        smallestInfiniteSet.heap.Push(i)
        smallestInfiniteSet.mp[i] = true
    }
    return smallestInfiniteSet
}

func (this *SmallestInfiniteSet) PopSmallest() int {
    this.mp[this.heap[0]] = false
    return this.heap.Pop()
}

func (this *SmallestInfiniteSet) AddBack(num int) {
    if !this.mp[num] {
        this.heap.Push(num)
        this.mp[num] = true
    }
}

func (h Heap) swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}
func (h Heap) less(i, j int) bool {
    return h[i] < h[j]
}
func (h Heap) up(i int) {
    father := (i - 1) / 2
    if father >= 0 && h.less(i, father) {
        h.swap(i, father)
        h.up(father)
    }
}
func (h Heap) down(i int) {
    smallest := i
    left := 2*i + 1
    right := 2*i + 2
    if left < len(h) && h.less(left, smallest) {
        smallest = left
    }
    if right < len(h) && h.less(right, smallest) {
        smallest = right
    }
    if smallest != i {
        h.swap(smallest, i)
        h.down(smallest)
    }
}
func (h *Heap) Push(v int) {
    *h = append(*h, v)
    h.up(len(*h) - 1)
}
func (h *Heap) Remove(i int) (int, bool) {
    if i < 0 || i >= len(*h) {
        return -1, false
    }
    x := (*h)[i]
    h.swap(i, len(*h)-1)
    *h = (*h)[:len(*h)-1]
    if i != len(*h) {
        h.down(i)
    }
    return x, true
}
func (h *Heap) Pop() int {
    x, _ := h.Remove(0)
    return x
}
// 写法二：优化
type SmallestInfiniteSet struct {
    heap Heap
    mp   map[int]bool
    idx  int
}

func Constructor() SmallestInfiniteSet {
    smallestInfiniteSet := SmallestInfiniteSet{}
    smallestInfiniteSet.mp = map[int]bool{}
    smallestInfiniteSet.idx = 1
    return smallestInfiniteSet
}

func (this *SmallestInfiniteSet) PopSmallest() int {
    res := -1
    if len(this.heap) != 0 {
        this.mp[this.heap[0]] = false
        res = this.heap.Pop()
    } else {
        res = this.idx
        this.idx++
    }
    return res
}

func (this *SmallestInfiniteSet) AddBack(num int) {
    if num >= this.idx || this.mp[num] {
        return
    }
    if num == this.idx-1 {
        this.idx--
    } else {
        this.heap.Push(num)
        this.mp[num] = true
    }
}

时间复杂度：插入和取出的最坏复杂度为 O(logn)
空间复杂度：O(n)

最大子序列的分数

2542. 最大子序列的分数 - 力扣（LeetCode）

给定两个长度一样的数组，再给一个整数k，从第一个数组中选取长度为k的子序列，求出和，从第二个数组中选取子序列对应下标中的最小值；分数 = 和×最小值。返回最大分数

思路：排序+小顶堆

降序重排nums2下标，枚举nums2[ids]最小，小顶堆求nums1前k大

对第二个数组的下标按元素值从大到小排序
将下标数组中前k个下标对应的第一个数组中元素值求和并入堆，求出一个分数
从第k+1个元素开始枚举下标数组，若nums1中该下标对应元素大于堆顶，则替换堆顶，求出分数与当前最大分数比较

 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79


var heap []int

func maxScore(nums1 []int, nums2 []int, k int) int64 {
    // nums2下标降序重排
    ids := make([]int, len(nums1))
    for i := range ids {
        ids[i] = i
    }
    sort.Slice(ids, func(i, j int) bool {
        return nums2[ids[i]] > nums2[ids[j]]
    })
    // 枚举nums2[ids]最小 小顶堆求nums1前k大
    res := 0
    sum := 0
    heap = []int{}
    for i, v := range ids {
        if i < k {
            sum += nums1[v]
            Push(nums1[v])
            if i == k-1 {
                res = sum * nums2[v]
            }
        } else if nums1[v] > heap[0] {
            sum += nums1[v] - heap[0]
            Pop()
            Push(nums1[v])
            res = max(res, sum*nums2[v])
        }
    }
    return int64(res)
}
func swap(i, j int) {
    heap[i], heap[j] = heap[j], heap[i]
}
func less(i, j int) bool {
    return heap[i] < heap[j]
}
func up(i int) {
    father := (i - 1) / 2
    if father >= 0 && less(i, father) {
        swap(father, i)
        up(father)
    }
}
func down(i int) {
    smallest := i
    left := 2*i + 1
    right := 2*i + 2
    if left < len(heap) && less(left, smallest) {
        smallest = left
    }
    if right < len(heap) && less(right, smallest) {
        smallest = right
    }
    if smallest != i {
        swap(smallest, i)
        down(smallest)
    }
}
func Push(v int) {
    heap = append(heap, v)
    up(len(heap) - 1)
}
func remove(i int) (int, bool) {
    if i < 0 || i >= len(heap) {
        return -1, false
    }
    x := heap[i]
    swap(i, len(heap)-1)
    heap = heap[:len(heap)-1]
    if i != len(heap) {
        down(i)
    }
    return x, true
}
func Pop() int {
    x, _ := remove(0)
    return x
}

雇佣 K 位工人的总代价

2462. 雇佣 K 位工人的总代价 - 力扣（LeetCode）

给定一个数组表示每个工人的雇用费，给定一个整数k表示轮数，一个整数candidates表示候选人总数。每轮从前candidates个工人和后candidates个工人中选出最低工费的一位。候选人数不够时，直接选其中最小的即可。返回总工费。

思路：最小堆

两个最小堆，一个维护前面的，另一个维护后面的。初始时判断给定轮数是否能遍历完所有工人，若可以，则直接排序后返回最小k个数和即可。

 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84


type Heap []int

func totalCost(costs []int, k int, candidates int) int64 {
    res := 0
    if len(costs) < candidates*2+k {
        sort.Slice(costs, func(i, j int) bool {
            return costs[i] < costs[j]
        })
        for i := 0; i < k; i++ {
            res += costs[i]
        }
    } else {
        heap1 := Heap(costs[:candidates])
        heap2 := Heap(costs[len(costs)-candidates:])
        heap1.Init()
        heap2.Init()
        left, right := candidates, len(costs)-candidates-1
        for i := 0; i < k; i++ {
            if heap1[0] <= heap2[0] {
                res += heap1.Pop()
                heap1.Push(costs[left])
                left++
            } else {
                res += heap2.Pop()
                heap2.Push(costs[right])
                right--
            }
        }
    }
    return int64(res)
}
func (h Heap) swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}
func (h Heap) less(i, j int) bool {
    return h[i] < h[j]
}
func (h Heap) down(i int) {
    smallest := i
    left := 2*i + 1
    right := 2*i + 2
    if left < len(h) && h.less(left, smallest) {
        smallest = left
    }
    if right < len(h) && h.less(right, smallest) {
        smallest = right
    }
    if smallest != i {
        h.swap(i, smallest)
        h.down(smallest)
    }
}
func (h Heap) up(i int) {
    father := (i - 1) / 2
    if father >= 0 && h.less(i, father) {
        h.swap(father, i)
        h.up(father)
    }
}
func (h *Heap) Push(v int) {
    *h = append(*h, v)
    h.up(len(*h) - 1)
}
func (h *Heap) Remove(i int) (int, bool) {
    if i < 0 || i >= len(*h) {
        return -1, false
    }
    h.swap(i, len(*h)-1)
    x := (*h)[len(*h)-1]
    (*h) = (*h)[:len(*h)-1]
    if i != len(*h) {
        h.down(i)
    }
    return x, true
}
func (h *Heap) Pop() int {
    x, _ := h.Remove(0)
    return x
}
func (h Heap) Init() {
    for i := len(h)/2 - 1; i >= 0; i-- {
        h.down(i)
    }
}

查找和最小的 K 对数字

373. 查找和最小的 K 对数字 - 力扣（LeetCode）

给定两个升序数组 nums1 和 nums2 , 以及一个整数 k 。定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 返回

思路：小顶堆

假设i,j最小——>可能的次小i,j+1、i+1,j入堆——>有数对重复入堆——>规定只入堆i,j+1——>初始入堆0,0后i一直为0不变——>初始入堆各个i,0

为描述方便，下文把nums1记作a，nums2记作b。

由于数组是有序的，(a[0],b[0])是和最小的数对，计入答案。次小的只能是 (a[0],b[1]) 或 (a[1],b[0])。

为了更高效地比大小，借助最小堆来优化：堆中保存下标(i, j)，堆顶是最小的 a[i]+b[j]。初始把 (0,0) 入堆。每次出堆时，可能成为次小数对的(i+1,j) 和 (i,j+1)入堆。

但这会导致一个问题：例如当 (1,0) 出堆时，会把 (1,1) 入堆；当 (0,1) 出堆时，也会把 (1,1) 入堆，这样堆中会有重复元素。为了避免有重复元素，规定 (i,j−1) 出堆时，将 (i,j) 入堆；而 (i−1,j) 出堆时只计入答案，其它什么也不做。

换句话说，在 (i,j) 出堆时，只需将 (i,j+1) 入堆，无需将 (i+1,j) 入堆。

但若按照该规则，初始仅把 (0,0) 入堆的话，只会得到 (0,1),(0,2),⋯这些下标对。

所以初始不仅要把 (0,0) 入堆，(1,0),(2,0),⋯ (min(k, n), 0) 这些都要入堆。

注意：

堆的初始长度设为 min(k, n)，保证当k<n时，只初始化k个数对，当n<k时，只能初始化n个数对
代码实现时，为了方便比较大小，实际入堆的是三元组 (i, j, a[i]+b[j])
也可以在循环的过程中去把 (i+1,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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84


type Heap [][]int

func kSmallestPairs(nums1 []int, nums2 []int, k int) [][]int {
    // 初始化一个大小为min(k, n)的小顶堆
    heap := make(Heap, min(k, len(nums1)))
    // 初始化加入(0,0,v)(1,0,v)...(min(k, n),0,v)
    for i := range heap {
        heap[i] = []int{i, 0, nums1[i] + nums2[0]}
    }
    // 维护小顶堆(取堆顶最小->可能的次小入堆)k次
    res := [][]int{}
    for cnt := 0; cnt < k; cnt++ {
        // 取堆顶(i, j)
        i, j := heap[0][0], heap[0][1]
        // (a[i], b[j])加入结果集
        res = append(res, []int{nums1[i], nums2[j]})
        heap.Pop()
        // 加入(i, j+1)
        // 防止越界
        if j+1 < len(nums2) {
            heap.Push(i, j+1, nums1[i]+nums2[j+1])
        }
    }
    return res
}
func (h Heap) swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h Heap) less(i, j int) bool {
    return h[i][2] < h[j][2]
}

func (h Heap) up(i int) {
    father := (i - 1) / 2
    if father >= 0 && h.less(i, father) {
        h.swap(father, i)
        h.up(father)
    }
}

func (h Heap) down(i int) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2
    if left < len(h) && h.less(left, largest) {
        largest = left
    }
    if right < len(h) && h.less(right, largest) {
        largest = right
    }
    if largest != i {
        h.swap(largest, i)
        h.down(largest)
    }
}

func (h *Heap) Push(i, j, v int) {
    *h = append(*h, []int{i, j, v})
    h.up(len(*h) - 1)
}

func (h *Heap) Remove(i int) ([]int, bool) {
    if i < 0 || i >= len((*h)) {
        return []int{}, false
    }
    h.swap(i, len(*h)-1)
    x := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    if i < len(*h) {
        father := (i - 1) / 2
        if father >= 0 && h.less(i, father) {
            h.up(i)
        } else {
            h.down(i)
        }
    }
    return x, true
}

func (h *Heap) Pop() []int {
    x, _ := h.Remove(0)
    return x
}

写法二：自实现小顶堆循环中加入(i+1, 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84


type Heap [][]int

func kSmallestPairs(nums1 []int, nums2 []int, k int) [][]int {
    // 初始化小顶堆加入(0,0,v)
    heap := Heap{[]int{0, 0, nums1[0] + nums2[0]}}
    // 维护小顶堆(取堆顶最小->可能的次小入堆)k次
    res := make([][]int, 0, k)
    for cnt := 0; cnt < k; cnt++ {
        // 取堆顶(i, j)
        i, j := heap[0][0], heap[0][1]
        // (a[i], b[j])加入结果集
        res = append(res, []int{nums1[i], nums2[j]})
        heap.Pop()
        // 当j=0时,加入(i+1, 0)
        if j == 0 && i+1 < len(nums1) {
            heap.Push(i+1, 0, nums1[i+1]+nums2[0])
        }
        // 加入(i, j+1)
        // 防止越界
        if j+1 < len(nums2) {
            heap.Push(i, j+1, nums1[i]+nums2[j+1])
        }
    }
    return res
}
func (h Heap) swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h Heap) less(i, j int) bool {
    return h[i][2] < h[j][2]
}

func (h Heap) up(i int) {
    father := (i - 1) / 2
    if father >= 0 && h.less(i, father) {
        h.swap(father, i)
        h.up(father)
    }
}

func (h Heap) down(i int) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2
    if left < len(h) && h.less(left, largest) {
        largest = left
    }
    if right < len(h) && h.less(right, largest) {
        largest = right
    }
    if largest != i {
        h.swap(largest, i)
        h.down(largest)
    }
}

func (h *Heap) Push(i, j, v int) {
    *h = append(*h, []int{i, j, v})
    h.up(len(*h) - 1)
}

func (h *Heap) Remove(i int) ([]int, bool) {
    if i < 0 || i >= len((*h)) {
        return []int{}, false
    }
    h.swap(i, len(*h)-1)
    x := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    if i < len(*h) {
        father := (i - 1) / 2
        if father >= 0 && h.less(i, father) {
            h.up(i)
        } else {
            h.down(i)
        }
    }
    return x, true
}

func (h *Heap) Pop() []int {
    x, _ := h.Remove(0)
    return x
}

写法三：标准库

 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


func kSmallestPairs(nums1 []int, nums2 []int, k int) [][]int {
    // 初始化小顶堆加入(0,0,v)
    h := Heap{[]int{0, 0, nums1[0] + nums2[0]}}
    // 维护小顶堆(取堆顶最小->可能的次小入堆)k次
    res := make([][]int, 0, k)
    for cnt := 0; cnt < k; cnt++ {
        // 取堆顶(i, j)
        p := heap.Pop(&h).([]int)
        i, j := p[0], p[1]
        // (a[i], b[j])加入结果集
        res = append(res, []int{nums1[i], nums2[j]})
        // 当j=0时,加入(i+1, 0)
        if j == 0 && i+1 < len(nums1) {
            heap.Push(&h, []int{i + 1, 0, nums1[i+1] + nums2[0]})
        }
        // 加入(i, j+1)
        // 防止越界
        if j+1 < len(nums2) {
            heap.Push(&h, []int{i, j + 1, nums1[i] + nums2[j+1]})
        }
    }
    return res
}

type Heap [][]int

func (h Heap) Len() int           { return len(h) }
func (h Heap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h Heap) Less(i, j int) bool { return h[i][2] < h[j][2] }
func (h *Heap) Push(v any)        { *h = append(*h, v.([]int)) }
func (h *Heap) Pop() any          { x := (*h)[len(*h)-1]; *h = (*h)[:len(*h)-1]; return x }

时间复杂度：O(klogmin(n,k))，其中 n 为 nums1的长度。为了得到 k 个数对，需要循环 k 次，每次出堆入堆的时间复杂度为 logmin(n,k)。所以总的时间复杂度为 O(klogmin(n,k))。
空间复杂度：O(min(n,k))。堆中至多有 O(min(n,k)) 个三元组。

丑数 II

264. 丑数 II - 力扣（LeetCode）

给一个整数 n ，找出并返回第 n 个丑数。丑数就是质因子只包含 2、3 和 5 的正整数

思路一：小顶堆+哈希表去重

根据题意，每个丑数都可以由其他较小的丑数通过乘以 2 或 3 或 5 得到。

所以，可以考虑使用一个优先队列保存所有的丑数，每次取出最小的那个，然后乘以 2 , 3 , 5 后放回队列。然而，这样做会出现重复的丑数

 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


type Heap []int

func nthUglyNumber(n int) int {
    // 初始化1入堆
    heap := Heap{1}
    // 哈希去重
    mp := map[int]bool{}
    // 不断循环直到取出第n个丑数
    for {
        // 取出当前堆中最小丑数
        curMin := heap.Pop()
        // 判是否取到第n个丑数
        n--
        if n == 0 {
            return curMin
        }
        // 得到三个候选丑数
        a, b, c := curMin*2, curMin*3, curMin*5
        // 去重后入堆
        if !mp[a] {
            heap.Push(a)
            mp[a] = true
        }
        if !mp[b] {
            heap.Push(b)
            mp[b] = true
        }
        if !mp[c] {
            heap.Push(c)
            mp[c] = true
        }
    }
}

时间复杂度：O(nlogn)。得到第 n 个丑数需要进行 n 次循环，每次循环都要从最小堆中取出 1 个元素以及向最小堆中加入最多 3 个元素，因此每次循环的时间复杂度是 O(log(3n)+3log(3n))=O(logn)，总时间复杂度是 O(nlogn)
空间复杂度：O(n)。空间复杂度主要取决于最小堆和哈希集合的大小，最小堆和哈希集合的大小都不会超过 3n

思路二：动态规划

思路一使用最小堆，会预先存储较多的丑数，维护最小堆的过程也导致时间复杂度较高。可以使用动态规划的方法进行优化。

dp[i]：第i个丑数
递推公式：dp[i] = min(dp[a]*2, dp[b]*3, dp[c]*5)
初始化：dp[1] = 1

利用三个指针生成丑数的算法流程：

初始化丑数列表 dp ，首个丑数为 1 ，三个指针 a , b, c 都指向首个丑数
开启循环生成丑数：
- 计算下一个丑数的候选集 dp[a]⋅2 , dp[b]⋅3 , dp[c]⋅5
- 选择丑数候选集中最小的那个作为下一个丑数，填入 dp
- 将被选中的丑数对应的指针向右移动一格
返回 dp 的最后一个元素即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func nthUglyNumber(n int) int {
    dp := make([]int, n+1)
    dp[1] = 1
    a, b, c := 1, 1, 1
    for i := 2; i <= n; i++ {
        dp[i] = min(dp[a]*2, dp[b]*3, dp[c]*5)
        if dp[i] == dp[a]*2 {
            a++
        }
        if dp[i] == dp[b]*3 {
            b++
        }
        if dp[i] == dp[c]*5 {
            c++
        }
    }
    return dp[n]
}

时间复杂度 O(n) ：计算 dp 列表需遍历 n−1 轮
空间复杂度 O(n) ：长度为 n 的 dp 列表使用 O(n) 的额外空间

天际线问题

218. 天际线问题 - 力扣（LeetCode）

给一组三元组[lefti, righti, heighti]表示多个建筑物的位置和高度，返回由这些建筑物形成的天际线，关键点是水平线段的左端点

思路：由相邻两个横坐标以及最大高度，可以确定一个矩形

题目要求输出每个矩形的“最上边”的左端点，同时跳过可由前一矩形“上边”延展而来的那些边。因此需要维护一个最大高度，可以使用优先队列（堆）

实现时，先记录下 buildings 中所有的左右端点横坐标及高度，并根据端点横坐标从小到大排序

先严格按照横坐标进行「从小到大」排序
对于某个横坐标而言，可能会同时出现多个点，应当按照如下规则进行处理：
- 优先处理左端点，再处理右端点
- 如果同样都是左端点，则按照高度「从大到小」进行处理（将高度增加到优先队列中）
- 如果同样都是右端点，则按照高度「从小到大」进行处理（将高度从优先队列中删掉）

在从前往后遍历处理时（遍历每个矩形），根据当前遍历到的点进行分情况讨论：

左端点：因为是左端点，必然存在一条从右延展的边，但不一定是需要被记录的边，因为在同一矩形中，只需要记录最上边的边。这时候可以将高度进行入队
右端点：此时意味着之前某一条往右延展的线结束了，这时候需要将高度出队（代表这条结束的线不再被考虑）

然后从优先队列中取出当前的最大高度，为了防止当前的线与前一矩形“最上边”延展而来的线重合，使用一个变量 prev 记录上一个记录的高度

 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98


type Heap []int

func getSkyline(buildings [][]int) [][]int {
    res := [][]int{}

    // 预处理点:记录所有左右端点的横坐标及高度
    // 为了方便排序,对于左端点令高度为负,对于右端点令高度为正
    pos := [][]int{}
    for _, building := range buildings {
        pos = append(pos, []int{building[0], -building[2]})
        pos = append(pos, []int{building[1], building[2]})
    }
    // 先按照横坐标升序重排
    // 若横坐标相同,则左端点在前
    // 若同为左端点,则按原高度大的在前
    // 若同为右端点,则按原高度小的在前
    sort.Slice(pos, func(i, j int) bool {
        if pos[i][0] != pos[j][0] {
            return pos[i][0] < pos[j][0]
        }
        return pos[i][1] < pos[j][1]
    })

    // 大顶堆
    heap := Heap{}
    // 记录上一个记录的高度
    prev := 0
    heap.Push(prev)
    // 遍历所有预处理后的点
    for _, p := range pos {
        if p[1] < 0 {
            // 若为左端点,则高度入堆
            heap.Push(-p[1])
        } else {
            // 若为右端点,则高度出堆
            for i, v := range heap {
                if v == p[1] {
                    heap.Remove(i)
                    break
                }
            }
        }
        // 若当前最高高度不与前一矩形“最上边”延展而来的那些边重合,则记录
        if heap[0] != prev {
            res = append(res, []int{p[0], heap[0]})
            prev = heap[0]
        }
    }
    return res
}
func (h Heap) swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}
func (h Heap) less(i, j int) bool {
    return h[i] > h[j]
}
func (h Heap) up(i int) {
    father := (i - 1) / 2
    if father >= 0 && h.less(i, father) {
        h.swap(i, father)
        h.up(father)
    }
}
func (h Heap) down(i int) {
    biggest := i
    left := i*2 + 1
    right := i*2 + 2
    if left < len(h) && h.less(left, biggest) {
        biggest = left
    }
    if right < len(h) && h.less(right, biggest) {
        biggest = right
    }
    if biggest != i {
        h.swap(i, biggest)
        h.down(biggest)
    }
}
func (h *Heap) Push(v int) {
    *h = append(*h, v)
    h.up(len(*h) - 1)
}
func (h *Heap) Remove(i int) (int, bool) {
    if i < 0 || i >= len(*h) {
        return -1, false
    }
    x := (*h)[i]
    h.swap(i, len(*h)-1)
    (*h) = (*h)[:len(*h)-1]
    if i != len(*h) {
        h.down(i)
    }
    return x, true
}
func (h *Heap) Pop() int {
    x, _ := h.Remove(0)
    return x
}

滑动窗口中位数

480. 滑动窗口中位数 - 力扣（LeetCode）

给一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

思路：本题是「295. 数据流的中位数」的进阶版本

大顶堆保存前半部分，小顶堆保存后半部分，保持大顶堆元素个数比小顶堆元素个数不多于2个，小顶堆元素不多于大顶堆元素

由于堆不支持按值移除元素，所以可以使用「延迟删除」，用哈希表记录每个元素还需要被删除多少次，每次更新堆顶时判断是否需要被删除

由于删除元素改变了元素个数，所以也需要保持大顶堆元素个数比小顶堆元素个数不多于2个，小顶堆元素不多于大顶堆元素

可以编写一个「保持平衡」函数，维持大顶堆元素个数比小顶堆元素个数不多于2个，小顶堆元素不多于大顶堆元素

「清除无效堆顶」函数只需要在移除堆顶元素时，循环判新堆顶是否有效并清除，直到堆顶有效

自定义切片长度，记录切片逻辑长度（不包括延迟删除），小于等于实际长度

注意：

由于是延迟删除，所以在标记删除元素时就要修改堆大小，避免影响「保持平衡」
在新入堆元素后，「保持平衡」中对移除堆顶元素的堆调用「清除无效堆顶」函数
由于堆中存在延迟删除元素，所以不能切片的长度属性判窗口内元素奇偶，可以之间用k；保持平衡函数中使用自定义切片长度
「清除无效堆顶」中循环终止条件是切片实际长度为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
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166


type Heap []int

var heap1 Heap
var heap2 Heap
var length1 int
var length2 int
var mp map[int]int
var winLength int

func medianSlidingWindow(nums []int, k int) []float64 {
    heap1, heap2 = Heap{}, Heap{}
    length1, length2 = 0, 0
    mp = map[int]int{}
    winLength = k
    // 初始化窗口
    for i := 0; i < k; i++ {
        // 元素入堆并保持平衡并保证堆顶有效
        insert(nums[i])
    }
    res := make([]float64, 1, len(nums)-k+1)
    res[0] = getMedian()
    // 移动窗口遍历nums
    for i := k; i < len(nums); i++ {
        insert(nums[i])
        // 标记删除元素
        erase(nums[i-k])
        // 得到当前窗口中位数
        res = append(res, getMedian())
    }
    return res
}

// 入堆并保持平衡
func insert(v int) {
    if len(heap1) == 0 || v <= heap1[0] {
        heap1.Push(v, true)
        length1++
    } else {
        heap2.Push(v, false)
        length2++
    }
    // 每添加一个元素都保持平衡
    makeBalance()
}

// 保持平衡并保证堆顶有效
func makeBalance() {
    if length1-length2 > 1 {
        heap2.Push(heap1.Pop(true), false)
        length1--
        length2++
        // 大顶堆堆顶元素被移除，需要判断新堆顶是否需要删除
        // 被大顶推移除的堆顶一定有效，所以不需要判小顶堆堆顶是否有效
        heap1.Prune(true)
    } else if length1 < length2 {
        heap1.Push(heap2.Pop(false), true)
        length2--
        length1++
        // 小顶堆堆顶元素被移除，需要判断新堆顶是否需要删除
        // 被小顶推移除的堆顶一定有效，所以不需要判大顶堆堆顶是否有效
        heap2.Prune(false)
    }
}

// 返回中位数
func getMedian() float64 {
    if winLength%2 == 1 {
        return float64(heap1[0])
    }
    return (float64(heap1[0]) + float64(heap2[0])) / 2.0
}

func erase(v int) {
    mp[v]++
    if v <= heap1[0] {
        // 更新逻辑长度
        length1--
        if v == heap1[0] {
            // 要延迟删除的元素就是堆顶元素,在Prune中更新哈希表后出堆
            heap1.Prune(true)
        }
    } else {
        length2--
        if v == heap2[0] {
            heap2.Prune(false)
        }
    }
    // 由于可能删除元素，所以需要保持平衡
    makeBalance()
}

func (h *Heap) Prune(sign bool) {
    for len(*h) > 0 {
        // 判堆顶是否无效
        if v, ok := mp[(*h)[0]]; ok {
            // 更新哈希表
            if v > 1 {
                mp[(*h)[0]]--
            } else {
                delete(mp, (*h)[0])
            }
            // 出堆
            h.Pop(sign)
        } else {
            break
        }
    }
}

func (h Heap) swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h Heap) less(i, j int, sign bool) bool {
    if sign {
        return h[i] > h[j]
    }
    return h[i] < h[j]
}

func (h Heap) up(i int, sign bool) {
    father := (i - 1) / 2
    if father >= 0 && h.less(i, father, sign) {
        h.swap(i, father)
        h.up(father, sign)
    }
}

func (h Heap) down(i int, sign bool) {
    est := i
    left := i*2 + 1
    right := i*2 + 2
    if left < len(h) && h.less(left, est, sign) {
        est = left
    }
    if right < len(h) && h.less(right, est, sign) {
        est = right
    }
    if est != i {
        h.swap(est, i)
        h.down(est, sign)
    }
}

func (h *Heap) Push(v int, sign bool) {
    (*h) = append((*h), v)
    h.up(len(*h)-1, sign)
}

func (h *Heap) Remove(i int, sign bool) (int, bool) {
    if i < 0 || i >= len(*h) {
        return -1, false
    }
    x := (*h)[i]
    h.swap(i, len(*h)-1)
    (*h) = (*h)[:len(*h)-1]
    if i != len(*h) {
        h.down(i, sign)
    }
    return x, true
}

func (h *Heap) Pop(sign bool) int {
    x, _ := h.Remove(0, sign)
    return x
}

时间复杂度：O(nlogn)。insert(num) 和 erase(num) 的单次时间复杂度为 O(logn)，getMedian() 的单次时间复杂度为 O(1)。因此总时间复杂度为 O(nlogn)
空间复杂度：O(n)。即为 small，large 和 delayed 需要使用的空间