面试必刷TOP101：堆、栈、队列（42-49，Python实现）

42.用两个栈实现队列（小试牛刀）

step 1：push操作就正常push到第一个栈末尾。
step 2：pop操作时，优先将第一个栈的元素弹出，并依次进入第二个栈中。
step 3：第一个栈中最后取出的元素也就是最后进入第二个栈的元素就是队列首部元素，要弹出，此时在第二个栈中可以直接弹出。
step 4：再将第二个中保存的内容，依次弹出，依次进入第一个栈中，这样第一个栈中虽然取出了最里面的元素，但是顺序并没有变。

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        self.stack1.append(node)
    def pop(self):
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        res = self.stack2.pop()
        while self.stack2:
            self.stack1.append(self.stack2.pop())
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度：push 的时间复杂度为 $O(1)$，pop的时间复杂度为 $O(n)$，push是直接加到栈尾，相当于遍历了两次栈。
空间复杂度：$O(n)$，借助了另一个辅助栈空间。

43.包含min函数的栈（小试牛刀）

step 1：使用一个栈记录进入栈的元素，正常进行push、pop、top操作。
step 2：使用另一个栈记录每次push进入的最小值。
step 3：每次push元素的时候与第二个栈的栈顶元素比较，若是较小，则进入第二个栈，若是较大，则第二个栈的栈顶元素再次入栈，因为即便加了一个元素，它依然是最小值。于是，每次访问最小值即访问第二个栈的栈顶。

class Solution:
    def __init__(self):
        self.stack1 = [] # 该栈用于记录进栈的元素，正常进行 push、pop、top 操作
        self.stack2 = [] # 该栈用于记录每次 push 进入的最小值
    def push(self, node):
        self.stack1.append(node)
        if len(self.stack2) == 0 or node < self.stack2[-1]:
            self.stack2.append(node)
        else:
            self.stack2.append(self.stack2[-1])
    def pop(self):
        self.stack1.pop()
        self.stack2.pop()
    def top(self):
        return self.stack1[-1]
    def min(self):
        return self.stack2[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度：$O(1)$，每个函数访问都是直接访问，无循环。
空间复杂度：$O(n)$，s1 为必要空间，s2 为辅助空间。

44.有效括号序列（小试牛刀）

step 1：创建辅助栈，遍历字符串。
step 2：每次遇到小括号的左括号、中括号的左括号、大括号的左括号，就将其对应的右括号加入栈中，期待在后续遇到。
step 3：如果没有遇到左括号但是栈为空，说明直接遇到了右括号，不合法。
step 4：其他情况下，如果遇到右括号，刚好会与栈顶元素相同，弹出栈顶元素继续遍历。
step 5：理论上，只要括号是匹配的，栈中元素最后是为空的，因此检查栈是否为空即可最后判断是否合法。

class Solution:
    def isValid(self , s: str) -> bool:
        a = []
        for i in range(len(s)):
            if s[i] == '(' or s[i] == '[' or s[i] == '{':
                a.append(s[i])
            elif len(a) == 0:
                return False
            elif s[i] == ')':
                if a[-1] == '(': 
                    a.pop() 
                else: 
                    return False
            elif s[i] == ']':
                if a[-1] == '[': 
                    a.pop() 
                else: 
                    return False
            elif s[i] == '}':
                if a[-1] == '{': 
                    a.pop()
                else: 
                    return False
        return len(a) == 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

代码优化后。

class Solution:
    def isValid(self , s: str) -> bool:
        a = []
        for i in range(len(s)):
            if s[i] == '(':
                a.append(')')
            elif s[i] == '[':
                a.append(']')
            elif s[i] == '{':
                a.append('}')
            elif len(a) == 0:
                return False
            elif s[i] == a[-1]:
                a.pop()
        return len(a) == 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度：$O(n)$，其中 n 为字符串长度，遍历整个字符串。
空间复杂度：$O(n)$，最坏情况下栈空间中记录整个字符串长度的右括号。

45.滑动窗口的最大值（小试牛刀）

45.1 暴力法

未AC通过，仅提供一种思路。

class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        a = []
        if size <= len(num) and size != 0:
            for i in range(len(num)-size+1):
                # 寻找每个窗口的最大值
                max_num = 0
                for j in range(i, i+size):
                    max_num = max(max_num,num[j])
                a.append(max_num)
        return a
1
2
3
4
5
6
7
8
9
10
11

时间复杂度：$O(nm)$，其中 n 为数组长度，m 为窗口长度，双层 for 循环。
空间复杂度：$O(1)$，没有使用额外的辅助空间，暂存的结果 res 不算入空间开销。

45.2 双向队列

我们都知道，若是一个数字A进入窗口后，若是比窗口内其他数字都大，那么这个数字之前的数字都没用了，因为它们必定会比A早离开窗口，在A离开之前都争不过A，所以A在进入时依次从尾部排除掉之前的小值再进入，而每次窗口移动要弹出窗口最前面值，因此队首也需要弹出，所以我们选择双向队列。

step 1：维护一个双向队列，用来存储数列的下标。
step 2：首先检查窗口大小与数组大小。
step 3：先遍历第一个窗口，如果即将进入队列的下标的值大于队列后方的值，依次将小于的值拿出来去掉，再加入，保证队列是递增序。
step 4：遍历后续窗口，每次取出队首就是最大值，如果某个下标已经过了窗口，则从队列前方将其弹出。
step 5：对于之后的窗口，重复step 3，直到数组结束。

from collections import deque
class Solution:
    def maxInWindows(self , num: List[int], size: int) -> List[int]:
        res = []
        if size <= len(num) and size != 0:
            # 双向队列，用来存储数列的下标
            dq = deque()
            # 先遍历一个窗口
            for i in range(size):
                # 去掉比自己先进队列的小于自己的值
                while len(dq) != 0 and num[dq[-1]] < num[i]:
                    dq.pop()
                dq.append(i)
            # 遍历后续数组元素
            for i in range(size, len(num)):
                res.append(num[dq[0]])
                while len(dq) != 0 and dq[0] < i-size+1:
                    # 弹出窗口移走后的值
                    dq.popleft()
                # 加入新的值前，去掉比自己先进队列的小于自己的值
                while len(dq) != 0 and num[dq[-1]] < num[i]:
                    dq.pop()
                dq.append(i)
            res.append(num[dq[0]])
        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

时间复杂度：$O(n)$，数组长度为 n，只遍历一遍数组。
空间复杂度：$O(m)$，窗口长度 m，双向队列最长时，将窗口填满。

46.最小的K个数（小试牛刀）

46.1 sort排序

class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        input.sort()
        return input[0:k]
1
2
3
4

时间复杂度：$O(nlo{g}_{2}n)$，sort 函数属于优化后的快速排序，复杂度为$O(nlo{g}_{2}n)$。
空间复杂度：$O(1)$，无额外辅助空间使用。

46.2 堆排序

要找到最小的k个元素，只需要准备k个数字，之后每次遇到一个数字能够快速的与这k个数字中最大的值比较，每次将最大的值替换掉，那么最后剩余的就是k个最小的数字了。

如何快速比较k个数字的最大值，并每次替换成较小的新数字呢？我们可以考虑使用优先队列（大根堆），只要限制堆的大小为k，那么堆顶就是k个数字的中最大值，如果需要替换，将这个最大值拿出，加入新的元素就好了。

step 1：利用input数组中前k个元素，构建一个大小为k的大顶堆，堆顶为这k个元素的最大值。
step 2：对于后续的元素，依次比较其与堆顶的大小，若是比堆顶小，则堆顶弹出，再将新数加入堆中，直至数组结束，保证堆中的k个最小。
step 3：最后将堆顶依次弹出即是最小的k个数。

import heapq # 默认是小根堆，所以每次输入要乘以-1
class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        res, pq = [], []
        if len(input) >= k and k != 0:
            # 构造一个k个大小的堆
            for i in range(k):
                heapq.heappush(pq, (-1 * input[i]))
            for i in range(k,len(input)):
                # 较小的元素入堆
                if (-1 * pq[0]) > input[i]:
                    heapq.heapreplace(pq, (-1 * input[i]))
            # 堆中元素取出数组
            for i in range(k):
                res.append(-1 * pq[0])
                heapq.heappop(pq)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度：$O(nlo{g}_{2}k)$，构建和维护大小为 k 的堆，需要 $lo{g}_{2}k$，加上遍历整个数组。
空间复杂度：$O(k)$，堆空间为 k 个元素。

47.寻找第K大（小试牛刀）

47.1 sort排序

class Solution:
    def findKth(self , a: List[int], n: int, K: int) -> int:
        a.sort()
        return a[-K]
1
2
3
4

时间复杂度：$O(nlo{g}_{2}n)$，sort 函数属于优化后的快速排序，复杂度为$O(nlo{g}_{2}n)$。
空间复杂度：$O(1)$，无额外辅助空间使用。

47.2 快排+二分查找

本题需要使用快速排序的思想，快速排序：每次移动，可以找到一个标杆元素，然后将大于它的移到左边，小于它的移到右边，由此整个数组划分成为两部分，然后分别对左边和右边使用同样的方法进行排序，不断划分左右子段，直到整个数组有序。这也是分治的思想，将数组分化成为子段，分而治之。
（1）放到这道题中，如果标杆元素左边刚好有 k−1 个比它大的，那么该元素就是第 k 大。
（2）如果它左边的元素比 k−1 少，说明第 k 大在其右边，直接二分法进入右边，不用管标杆元素左边。
（3）同理如果它右边的元素比 k−1 少，那第 k 大在其左边，右边不用管。

step 1：进行一次快排，大元素在左，小元素在右，得到的标杆 j 点。在此之前要使用随机数获取标杆元素，防止数据分布导致每次划分不能均衡。
step 2：如果 j + 1 = k，那么 j 点就是第 K 大。
step 3：如果 j + 1 > k，则第 k 大的元素在左半段，更新 high = j - 1，执行 step 1。
step 4：如果 j + 1 < k，则第 k 大的元素在右半段，更新 low = j + 1, 再执行 step 1。

import random
class Solution:
    def partition(self, a: List[int], low: int, high: int, k: int) -> int:
        # 随机快排划分，防止数据分布导致每次划分不能均衡
        x = random.randint(0,10000)
        a[low], a[x % (high-low+1) + low] = a[x % (high-low+1) + low], a[low]
        v = a[low] # 初始标杆元素
        i = low + 1
        j = high
        # 快速排序
        while True:
            # 小的在右边
            while j >= low + 1 and a[j] < v:
                j = j - 1
            # 大的在左边
            while i <= high and a[i] > v:
                i = i + 1
            if i > j:
                break
            # 交换左右两侧的数
            a[i], a[j] = a[j], a[i]
            # 交换结束后，i-1，j+1
            i = i + 1
            j = j - 1
        # 一轮排序结束后，定下一个值的位置
        a[low], a[j] = a[j], a[low]
        # 从0开始，所以为第j+1大
        if j + 1 == k:
            return a[j]
        # 左边的元素比 k 少，说明第 k 大在右边，直接二分法进入右边
        elif j + 1 < k:
            return self.partition(a, j+1, high, k)
        # 右边的元素比 k 少，说明第 k 大在左边，直接二分法进入左边
        else:
            return self.partition(a, low, j-1, k)
            
    def findKth(self , a: List[int], n: int, K: int) -> int:
        return self.partition(a, 0, n-1, 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

时间复杂度：O(n)，利用二分法缩短了时间：T(2/N) + T(N/4) + T(N/8) + … = T(N)。
空间复杂度：O(n)，递归栈最大深度。

48.数据流中的中位数（小试牛刀）

48.1 sort排序

class Solution:
    def __init__(self):
        self.a = []
    def Insert(self, num):
        self.a.append(num)
    def GetMedian(self):
        n = len(self.a)
        self.a.sort()
        if n % 2 == 1:
            return self.a[n//2]
        else:
            return (self.a[n//2] + self.a[n//2 - 1]) / 2.0
1
2
3
4
5
6
7
8
9
10
11
12

48.2 插入排序

第一种方法，每次找中位数都要排序，有点浪费时间。可以通过插入排序的思想，建立起有序数列。

传统的寻找中位数的方法便是排序之后，取中间值或者中间两位的平均即可。但是这道题因为数组在不断增长，每增长一位便需要排一次，很浪费时间，于是可以考虑在增加数据的同时将其有序化，这个过程就让我们想到了插入排序：对于每个输入的元素，遍历已经有序的数组，将其插入到属于它的位置。

step 1：用一数组存储输入的数据流。
step 2：Insert函数在插入的同时，遍历之前存储在数组中的数据，按照递增顺序依次插入，如此一来，加入的数据流便是有序的。
step 3：GetMedian函数可以根据下标直接访问中位数，分为数组为奇数个元素和偶数个元素两种情况。记得需要类型转换为double。

class Solution:
    def __init__(self):
        self.a = []
    def Insert(self, num):
        if len(self.a) == 0:
            self.a.append(num)
        else:
            i = 0
            # 遍历找到插入点
            while i < len(self.a):
                if num <= self.a[i]:
                    break
                i = i + 1
            self.a.insert(i,num)
    def GetMedian(self):
        n = len(self.a)
        if n % 2 == 1:
            return self.a[n//2]
        else:
            return (self.a[n//2] + self.a[n//2 - 1]) / 2.0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度：Insert 函数 O(n)，不管遍历还是插入都是 O(n)，GetMedian 函数 O(1)，直接访问。
空间复杂度：O(n)，记录输入流的数组。

48.3 堆排序

除了插入排序，我们换种思路，因为插入排序每次要遍历整个已经有的数组，很浪费时间，有没有什么可以找到插入位置时能够更方便。

我们来看看中位数的特征，它是数组中间个数字或者两个数字的均值，它是数组较小的一半元素中最大的一个，同时也是数组较大的一半元素中最小的一个。那我们只要每次维护最小的一半元素和最大的一半元素，并能快速得到它们的最大值和最小值，那不就可以了嘛。这时候就可以想到了堆排序的优先队列。

step 1：我们可以维护两个堆，分别是大顶堆min，用于存储较小的值，其中顶部最大；小顶堆max，用于存储较大的值，其中顶部最小，则中位数只会在两个堆的堆顶出现。
step 2：我们可以约定奇数个元素时取大顶堆的顶部值，偶数个元素时取两堆顶的平均值，则可以发现两个堆的数据长度要么是相等的，要么奇数时大顶堆会多一个。
step 3：每次输入的数据流先进入大顶堆排序，然后将大顶堆的最大值弹入小顶堆中，完成整个的排序。
step 4：但是因为大顶堆的数据不可能会比小顶堆少一个，因此需要再比较二者的长度，若是小顶堆长度小于大顶堆，需要从大顶堆中弹出最小值到大顶堆中进行平衡。

import heapq # 默认是小顶堆
class Solution:
    def __init__(self):
        # 存储了右侧较大部分的元素，为小顶堆
        self.max = []
        # 存储了左侧较小部分的元素，为大顶堆
        self.min = []
    def Insert(self, num):
        # 先加入较小部分
        heapq.heappush(self.min, (-1*num))
        # 将较小部分的最大值取出，送到较大部分
        heapq.heappush(self.max, (-1*self.min[0]))
        heapq.heappop(self.min)
        # 平衡两个堆的数量
        if len(self.min) < len(self.max):
            heapq.heappush(self.min, (-1*self.max[0]))
            heapq.heappop(self.max)
        
    def GetMedian(self):
        if len(self.min) > len(self.max):
            return -1.0 * self.min[0]
        else:
            return (-1 * self.min[0]  + self.max[0]) / 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度：Insert函数$O(lo{g}_{2}n)$，维护堆的复杂度，GetMedian函数 O(1)，直接访问。
空间复杂度：$O(n)$，两个堆的空间，虽是两个，但是一个堆最多 n/2。

49.表达式求值（小试牛刀）

对于上述两个要求，我们要考虑的是两点，一是处理运算优先级的问题，二是处理括号的问题。

处理优先级问题，那必定是乘号有着优先运算的权利，加号减号先一边看，我们甚至可以把减号看成加一个数的相反数，则这里只有乘法和加法，那我们优先处理乘法，遇到乘法，把前一个数和后一个数乘起来，遇到加法就把这些数字都暂时存起来，最后乘法处理完了，就剩余加法，把之前存起来的数字都相加就好了。

处理括号的问题，我们可以将括号中的部分看成一个新的表达式，即一个子问题，因此可以将新的表达式递归地求解，得到一个数字，再运算：
（1）终止条件： 每次遇到左括号意味着进入括号子问题进行计算，那么遇到右括号代表这个递归结束。
（2）返回值： 将括号内部的计算结果值返回。
（3）本级任务： 遍历括号里面的字符，进行计算。

step 1：使用栈辅助处理优先级，默认符号为加号。
step 2：遍历字符串，遇到数字，则将连续的数字字符部分转化为 int 型数字。
step 3：遇到左括号，则将括号后的部分送入递归，处理子问题；遇到右括号代表已经到了这个子问题的结尾，结束继续遍历字符串，将子问题的加法部分相加为一个数字，返回。
step 4：当遇到符号的时候如果是 +，得到的数字正常入栈，如果是 -，则将其相反数入栈，如果是*，则将栈中内容弹出与后一个元素相乘再入栈。
step 5：最后将栈中剩余的所有元素，进行一次全部相加。

class Solution:
    def solve(self , s: str) -> int:
        s = s.strip() # 去掉前后空格
        stack = []    # 保存每一小步的结果
        res = 0       # 最后求和用
        num = 0       # 每一小步的运算结果
        sign = '+'    # 记录符号变化
        index = 0     # 指针
        while index < len(s):
            if s[index] == ' ':
                index = index + 1
                continue
            # 遇到左括号
            if s[index] == '(':
                end = index + 1
                lens = 1 # 记录遇到了多少对括号
                while lens > 0:
                    if s[end] == '(':
                        lens = lens + 1
                    if s[end] == ')': # 遇到右括号，就消掉一个
                        lens = lens - 1
                    end = end + 1
                # 将括号视为子问题进入递归
                num = self.solve(s[index+1:end-1])
                index = end - 1
                continue
            # 字符数字转换成 int 数字
            if '0' <= s[index] <= '9':
                num = num * 10 + int(s[index])
            # 根据符号运算
            if not '0' <= s[index] <= '9' or index == len(s)-1:
                if sign == '+':
                    stack.append(num)
                elif sign == '-':
                    stack.append(-1 * num)
                elif sign == '*':
                    stack.append(stack.pop() * num)
                num = 0 # 算完一小步后，num 清零
                sign = s[index] 
            # 指针后移
            index = index + 1 
        # 最后，栈中元素相加
        while stack:
            res = res + stack.pop()
        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
40
41
42
43
44
45

时间复杂度：O(n)，n 为字符串长度，相当于遍历一遍字符串全部元素。
空间复杂度：O(n)，辅助栈和递归栈的空间