详解基于栈的算法

reference

单调栈技巧总结

单调栈详解

数据结构 | 栈都知道，单调栈有了解吗？

单调栈算法

什么是单调栈算法

单调栈：要求每次入栈的元素必须要有序（如果新元素入栈不符合要求，则将之前的元素出栈，直到符合要求再入栈），使之形成单调递增/单调递减的一个栈。

分类：

• 单调递增栈（按出栈顺序递增，即是一个递减的数组）：只有比栈顶小的才能入栈，否则就把栈顶出栈一直到没有比该值更大的，再入栈。出栈时可能会有一些计算。
  单调递减栈（按出栈顺序递减，即是一个递增的数组）：只有比栈顶大的才能入栈，否则就把栈顶出栈一直到没有比该值更小的，再入栈。

适用条件

当我们需要++比较数组中前后元素的关++系时即更具体的是如下场景：

第一个大于 **

第一个小于 **

连续大于 **

连续小于 **

下一个大于 **

下一个小于 **

复杂度

时间复杂度 O(N)
空间复杂度 O(N)

如何实现

stack = []
# 假设是单调递减
for i in range(len(T)):
    while len(stack)>0 and T[i] < stack[-1]:
        stack.pop()
        # 进行相关的运算
    stack.append(T[i])
1
2
3
4
5
6
7

examples

股票价格跨度-leetcode-901

解题思路：
关键词：小于或等于今天价格的最大连续数，由此可见有必要使用单调栈来解决问题

# 典型的单调栈问题
class StockSpanner:
    def __init__(self):
        self.stack = []
    def next(self, price: int) -> int:
        weight = 1
        # 我们希望找到连续的比当前元素小的元素，也就是出栈是单调递增的
        # 所以数组是单减的，同时我们使用一个 weight 标识比当前值小的数目，我们用元组来标识栈中的每个元素
        while self.stack and self.stack[-1][0] <= price:
            weight += self.stack.pop()[1]
        self.stack.append((price, weight))
        return weight
1
2
3
4
5
6
7
8
9
10
11
12

每日温度-leetcode-739

解题思路：

和上面的「股票价格跨度」类似的问题：通过题目理解，我们发现其实是寻找下一个比当前元素大的元素的位置。

由此可以用单调栈来做，单调递增栈即单减列表。

时间复杂度：O(n)

空间复杂度：O(n)

class Solution:
    # 通过题目理解，我们发现其实是寻找下一个比当前元素大的元素的位置
    # 由此可以用单调栈来做，单调递增栈即单减列表
    # 解题思路和[股票价格跨度](https://leetcode.cn/problems/online-stock-span)相同
    # 时间复杂度：O(n)
    # 空间复杂度：O(n)
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        length, stack = len(temperatures), []
        res = [0] * length
        for i in range(length - 1, -1, -1):
            while len(stack) > 0 and stack[-1][0] <= temperatures[i]:
                stack.pop()
            if len(stack) > 0:
                res[i] = stack[-1][1] - i
            stack.append((temperatures[i], i))
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

下一个更大元素 I-leetcode-496 🌟🌟🌟

解题思路：
通过题目关键词：下一个更大，可以发现这个题可以用单调栈来解决

class Solution:
    # 从题目中我们知道这是要构建一个单调递减栈即出栈时是单减的，而整个数组是单增的
    # 假如我们要做一个单增栈呢，整个数组是单减的
    def nextGreaterElement0(self, nums1: List[int], nums2: List[int]) -> List[int]:
        res = []
        for i in range(len(nums1)):
            idx = nums2.index(nums1[i])
            if idx + 1 > len(nums2) - 1:
                res.append(-1)
                continue
            for j in range(idx + 1, len(nums2)):
                stack = [nums1[i]]
                while len(stack) > 0 and nums2[j] < stack[-1]:
                    stack.pop()
                if len(stack) > 0 and stack[-1] == nums1[i]:
                    res.append(nums2[j])
                    break
            if len(res) < i + 1:
                res.append(-1)
        return res

    # 上述的解决方法看起来复杂度还是很高，我们已经获悉 nums1和nums2中所有整数 互不相同
    # 问题就变成了如何求每个元素的右边第一个比它大的元素，因此我们使用单增栈即数组是单减的
    # 时间复杂度 O(max(m,n)) m n 分别是 nums1 nums2 的长度
    # 空间复杂度 O(max(m,n))
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack, map, res = [], {}, []
        for i in range(len(nums2) - 1, -1, -1):
            while len(stack) > 0 and stack[-1] <= nums2[i]:
                stack.pop()
            if len(stack) > 0:
                map[nums2[i]] = stack[-1]
            else:
                map[nums2[i]] = -1
            # print('====>', nums2[i], stack, map)
            stack.append(nums2[i])
        for i in range(len(nums1)):
            res.append(map[nums1[i]])
        return res
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

下一个更大元素 II-leetcode-503

解题思路：

其实是寻找下一个更大元素的变种

class Solution:
    # 以 [1,2,3] 为例 1 需遍历 2 3  1 2 3
    # 2 需遍历 3 1  2 3 1
    # 3 需遍历 1 2  3 1 2
    # 穷举下来我们需要遍历的实则是 1 2 3 1 2
    # [1,2,3,4,3] 需要遍历的则是 [1,2,3,4,3,1,2,3,4]
    # [2,3,4,-1,4]
    # 时间复杂度：O(n)
    # 空间复杂度：O(n)
    # 感谢 ac
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        length, stack = len(nums), []
        res = [-1] * length
        nums.extend(nums[0:(length - 1)])
        for i in range(len(nums) - 1, -1, -1):
            while len(stack) > 0 and nums[i] >= stack[-1]:
                stack.pop()
            if len(stack) > 0 and i < length:
                res[i] = stack[-1]
            stack.append(nums[i])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

去除重复字母-leetcode-316 🌟🌟🌟

解题思路：

题目因为出现字典序这个关键词，相当于希望整体列表有一定连续的顺序，因此可以考虑用单调栈解决，同时也要注意题目中的限制，是一个值得多做几次的题目。

class Solution:
    # 需要保证返回结果的字典序最小，也就是从左向右尽量是递增的，同时不影响相对位置
    # 所以我们可以用单减栈即单增数组来做，为了不将某些元素遗漏，可以提前收集每个字母的数量

    # 我们发现正是收集每个字母的数量这个做法导致题目最终没有通过，而我们可以通过检查 s 从 i 开始是否还有这个字母来判断
    # 这样就不容易出错了
    def removeDuplicateLetters(self, s: str) -> str:
        length, str_map, res, tmp_map = len(s), {}, "", {}
        for i in range(length):
            if s[i] in str_map:
                str_map[s[i]] = str_map[s[i]] + 1
            else:
                str_map[s[i]] = 1
        for i in range(length):
            if s[i] in res:
                str_map[s[i]] = str_map[s[i]] - 1
                continue
            while len(res) > 0 and res[-1] > s[i] and str_map[res[-1]] >= 1:
            # while len(res) > 0 and res[-1] > s[i] and res[-1] in s[i:]:
                res = res[:-1]
            res = res + s[i]
            str_map[s[i]] = str_map[s[i]] - 1
        return res

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

最短无序连续子数组-leetcode-581

解题思路

利用两个单调栈分别确定始末：

我们发现题目数组最终会升序排序，很自然的想到了单调栈

以 [2,6,4,8,10,9,15] 为例，正向我们构造一个单减栈，得到 start，注意像 [1, 3, 5, 4, 2]
这种数组，所以我们要遍历完所有元素才得到 start

反向我们构造一个单增栈，得到 end，同理拿到 end

class Solution:
    # 我们发现题目数组最终会升序排序，很自然的想到了单调栈
    # 时间复杂度 O(N)
    # 空间复杂度 O(N)
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        stack0, stack1, length = [], [], len(nums)
        start, end = length - 1, 0
        for i in range(length):
            while len(stack0) > 0 and stack0[-1][1] > nums[i]:
                start = min(start, stack0[-1][0])
                stack0.pop()
            stack0.append((i, nums[i]))
        for i in range(length - 1, -1, -1):
            while len(stack1) > 0 and stack1[-1][1] < nums[i]:
                end = max(end, stack1[-1][0])
                stack1.pop()
            stack1.append((i, nums[i]))
        # print("=====>", start, end)
        return end - start + 1 if end > start else 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

移掉 K 位数字-leetcode-402

解题思路：

这个题之前是使用其他方法做出来的，学习了单调栈之后可以使用单调栈的方法来做。

我们发现解题时总是希望移走排在前面的比较大的数字，所以

1. 方法 1：
   可以这样去思考这个问题，当第一个数比后一个数大的时候，这个数肯定要移走，否则保留

指针位置不变，再将移到当前位置的数和后一个数比较

如果到最后 k 仍未消零，则将最后的几位删掉即可

时间复杂度 O(N)

空间复杂度 O(1)
2. 方法 2：
我们可以用单调栈来解决

用单减栈即单增数组：1 4 pop 4 add 3，pop 3 add 2, pop 2 add 2

10200 1 pop 1 add 0，详情参考下面的代码

时间复杂度 O(N)

空间复杂度 O(N)

class Solution:
    # 可以这样去思考这个问题，当第一个数比后一个数大的时候，这个数肯定要移走，否则保留
    # 指针位置不变，再将移到当前位置的数和后一个数比较
    # 如果到最后 k 仍未消零，则将最后的几位删掉即可
    # 时间复杂度 O(N)
    # 空间复杂度 O(1)
    def removeKdigits1(self, num: str, k: int) -> str:
        n, i = len(num), 0
        if n <= k:
            return '0'
        while k > 0 and -1 < i < len(num) - 1:
            if num[i] > num[i + 1]:
                num = num[1:] if i == 0 else num[0:i] + num[i + 1:]
                k = k - 1
                i = i - 1 if i >= 1 else i
            elif num[i] < num[i + 1]:
                i = i + 1
            else:
                i = i + 1
        if k > 0:
            num = num[0:len(num) - k]
        while num[0] == '0' and len(num) > 1:
            num = num[1:]
        return num

    # 题目要求返回移除 k 个之后最小的数字
    # 1432219 如果移除 1 个 那肯定移除高位上的高的数  132219
    # 1432219 如果移除 2 个，12219
    # 我们发现解题时总是希望移走排在前面的比较大的数字，所以我们可以用单调栈来解决
    # 如果用单减栈即单增数组：1 4 pop 4 add 3，pop 3 add 2, pop 2 add 2
    # 10200 1 pop 1 add 0
    # 第二次练习，使用单减栈去解决问题
    def removeKdigits(self, num: str, k: int) -> str:
        stack, length, i = [], len(num), 0
        if k >= length:
            return '0'
        while i < length:
            while len(stack) > 0 and int(stack[-1]) > int(num[i]):
                if k == 0:
                    break
                else:
                    k = k - 1
                    stack.pop()
            if k == 0:
                break
            else:
                stack.append(num[i])
            i = i + 1
        # 因为我们已经拍好序了所以无需再反着来一遍
        if k == 0:
            nums = list(num)
            stack.extend(nums[i:])
        if k > 0:
            # return self.remove_zero(stack0[:len(stack0)-k])
            stack = stack[:len(stack) - k]
        while len(stack) > 0 and stack[0] == '0':
            stack = stack[1:]
        return ''.join(stack) if len(stack) > 0 else '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