栈与队列 Part02#

1
class Solution:
2
    def evalRPN(self, tokens: List[str]) -> int:
3
        stack = []
4
        for char in tokens:
5
            if char in "+-*/":
6
                right = stack.pop()
7
                left = stack.pop()
8
                if char == '+':
9
                    res = left + right
10
                    stack.append(res)
11
                elif char == '-':
12
                    res = left - right
13
                    stack.append(res)
14
                elif char == '*':
15
                    res = left * right
16
                    stack.append(res)
17
                else:
18
                    # 这里需要使用 int() 来确保结果是整数除法，
19
                    # 如果使用 // 会导致负数除法结果不正确
20
                    # 例如 -1 // 2 会得到 -1，而 int(-1 / 2) 会得到 0
21
                    res = int(left / right)
22
                    stack.append(res)
23
            else:
24
                stack.append(int(char))
25
        return stack.pop()

1
from collections import deque
2

3
class Solution:
4
    # 构造单调递减队列，每次入队列检查当前值和队列中最后一个值的大小关系
5
    # 当前值比队列中最后一个值大时，弹出队列中最后一个值
6
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
7
        wid = deque()
8
        n = len(nums)
9
        res = []
10
        for i in range(n):
11
            # 保持队列单调递减
12
            while wid and nums[i] > wid[-1]:
13
                wid.pop()
14
            wid.append(nums[i])
15

16
            # 如果滑动窗口已经满了，检查是否需要移除窗口最左边的元素
17
            if i >= k:
18
                if nums[i - k] == wid[0]:
19
                    wid.popleft()
20

21
            # 从第一个完整窗口开始记录结果
22
            if i >= k - 1:
23
                res.append(wid[0])
24
        return res

1
import heapq
2

3
class Solution:
4
    # 先使用 map 来记录每个元素的出现次数
5
    # 然后使用最小堆（优先队列）来维护前 k 个出现次数最多的元素
6
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
7
        count = {}
8
        for num in nums:
9
            count[num] = count.get(num, 0) + 1
10

11
        pq = []
12
        for key, value in count.items():
13
            # 维护一个小顶堆，堆的大小保持为 k
14
            heapq.heappush(pq, (value, key))
15
            if len(pq) > k:
16
                heapq.heappop(pq)
17

18
        res = [0] * k
19
        # 注意这里从堆中取出时是从小到大，需要逆序填入结果数组
20
        for i in range(k - 1, -1, -1):
21
            res[i] = heapq.heappop(pq)[1]
22
        return res