逆波兰表达式求值

题目链接
根据 逆波兰表示法，求表达式的值。
有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

  • 示例 1：
    输入: [“2”, “1”, “+”, “3”, “ * “]
    输出: 9
    解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
  • 示例 2：
    输入: [“4”, “13”, “5”, “/“, “+”]
    输出: 6
    解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
  • 示例 3：
    输入: [“10”, “6”, “9”, “3”, “+”, “-11”, “ * “, “/“, “ * “, “17”, “+”, “5”, “+”]
    输出: 22
    解释:该算式转化为常见的中缀算术表达式为：
1
2
3
4
5
6
7
((10 * (6 / ((9 + 3) * -11))) + 17) + 5       
= ((10 * (6 / (12 * -11))) + 17) + 5       
= ((10 * (6 / -132)) + 17) + 5     
= ((10 * 0) + 17) + 5     
= (0 + 17) + 5    
= 17 + 5    
= 22

逆波兰表达式：是一种后缀表达式，所谓后缀就是指运算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。（是一种二叉数树的后续遍历）
逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for i in tokens:
            if i == "+" or i == '-' or i == '*' or i == "/":
                a = stack.pop()
                b = stack.pop()
                if i == "+":
                    stack.append(a+b)
                elif i == "-":
                    stack.append(b-a)
                elif i == "*":
                    stack.append(a*b)
                elif i == "/":
                    stack.append(int(b/a)) # 向零取整用int（b/a）直接截断小数部分
            else :
                stack.append(int(i))
        return stack.pop()

使用栈来保存数字，遇到运算符就弹出栈顶的两个数字进行计算，然后把结果压回栈中。最后栈中剩下的数字就是结果。

滑动窗口最大值

题目链接
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。

  • 示例 1：
1
2
3
4
5
6
7
8
9
10
11
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
  • 示例 2：
1
2
输入：nums = [1], k = 1
输出：[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
from collections import deque

class Queue :
    def __init__ (self):
        self.que = deque()
    
    def pop(self,value): #这里啥时候队列可能为空呢
        if self.que and value == self.que[0]:#队列不为空且遍历的值等于队口
            self.que.popleft()   #弹的是最大（对头在左）
    def push(self,value):
        while self.que and value > self.que[-1]:
            self.que.pop()
        self.que.append(value)
    def get(self):
        return self.que[0]


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        que = Queue()
        result = []
        for i in range(k):
            que.push(nums[i])
        result.append(que.get())
        for i in range(k,len(nums)):
            que.pop(nums[i-k]) #例如加入第四个元素前要移除第一个
            que.push(nums[i])
            result.append(que.get())
        return result

下面是ai的带注释的

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
from collections import deque

class MonotonicQueue:  # 改名：明确是单调递减队列，避免语义混淆
    def __init__(self):
        self.que = deque()  # 存储 nums 的元素（也可存索引，更灵活）
    
    def remove_left(self, value):
        """
        滑动窗口移动时，移除窗口左边界的元素（仅当该元素是队首时，因为队首是最大值）
        此时队列可能为空：必须先判断 self.que 非空
        """
        if self.que and value == self.que[0]:  # 队列非空 + 左边界元素是队首（最大值）
            self.que.popleft()  # 弹出队首（移除窗口外的最大值）
    
    def push(self, value):
        """
        加入当前元素，维持队列单调递减：
        移除队列中所有比当前元素小的元素（这些元素不可能成为后续窗口的最大值）
        此时队列可能为空：空队列直接 append 即可
        """
        while self.que and self.que[-1] < value:  # 队列非空 + 队尾元素 < 当前元素
            self.que.pop()  # 移除队尾（从右弹出，deque.pop() 是O(1)）
        self.que.append(value)  # 加入当前元素，队列仍保持递减
    
    def get_max(self):
        """获取当前窗口最大值（队首），必须保证调用前队列非空"""
        return self.que[0]


class Solution:
    def maxSlidingWindow(self, nums, k):
        # 边界情况处理（避免队列空时调用 get_max）
        if not nums or k == 0 or k > len(nums):
            return []
        
        que = MonotonicQueue()
        result = []
        
        # 第一步：初始化第一个窗口（前 k 个元素）
        for i in range(k):
            que.push(nums[i])
        # 第一个窗口的最大值加入结果（此时队列非空，因为 k<=len(nums) 且 nums 非空）
        result.append(que.get_max())
        
        # 第二步：滑动窗口（从第 k 个元素开始，到最后一个元素）
        for i in range(k, len(nums)):
            # 1. 移除窗口左边界的元素（i-k 是当前窗口的左边界索引）
            left_value = nums[i - k]  # 窗口要移除的左边界元素
            que.remove_left(left_value)
            
            # 2. 加入当前窗口的右边界元素（第 i 个元素）
            que.push(nums[i])
            
            # 3. 记录当前窗口的最大值（队列非空）
            result.append(que.get_max())
        
        return result


# 测试案例
if __name__ == "__main__":
    s = Solution()
    print(s.maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))  # 输出 [3,3,5,5,6,7]（正确）
    print(s.maxSlidingWindow([], 3))  # 输出 []（边界处理）
    print(s.maxSlidingWindow([1], 1))  # 输出 [1]（边界处理）
    print(s.maxSlidingWindow([1,-1], 2))  # 输出 [1]（边界处理）

这道题是用单调队列来解决的，单调队列是指队列中的元素是单调递增或递减的。
那如何保证队列中的元素是单调递减的呢？
当有新元素加入时，我们将队列中所有比新元素小的元素都弹出，直到队列为空或者队列尾部的元素大于等于新元素为止。这样就保证了队列中的元素是单调递减的。

  • 关于我在视频弹幕上遇到的一个情况5231，其实解决这个的方式是在push方法中加入一个判断，当队列非空且队尾元素小于等于新元素时，弹出队尾元素，直到队列为空或者队列尾部的元素大于等于新元素为止。（这样3进去的之前2就被弹出了）
  • 为啥要判断队列非空？

    初始阶段：刚实例化 Queue 时（init 后），self.que = deque() 是空的，此时调用 pop/get 都会操作空队列。

    窗口滑动时移除元素后：比如窗口内所有元素都被 pop 方法移除（例如滑动窗口移动时，队首元素是前一个窗口的最大值，被弹出后队列无其他元素）。

    nums 数组本身为空或 k=0：当输入 nums = [] 或 k=0 时，循环不执行 push，队列始终为空。

前 K 个高频元素

题目链接

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

  • 输入: nums = [1,1,1,2,2,3], k = 2
  • 输出: [1,2]

示例 2:

  • 输入: nums = [1], k = 1
  • 输出: [1]

提示：

  • 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
  • 你的算法的时间复杂度必须优于 $O(n \log n)$ , n 是数组的大小。
  • 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
  • 你可以按任意顺序返回答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dir = {}
        for i in range(len(nums)):
            dir[nums[i]] = dir.get(nums[i],0) + 1 #key不存在就设为0，存在就加1
        que = []
        for key,value in dir.items():
            heapq.heappush(que,(value,key)) #注意value在前，因为按照value排序的
            if len(que) > k:
                heapq.heappop(que)
        result = [0] * k
        for i in range(k-1,-1,-1): #第一个-1取不到所以就是0开始
            result[i] = heapq.heappop(que)[1]
        return result

使用哈希表统计每个元素的频率，然后使用小顶堆维护前 k 个高频元素。
小顶堆的大小为 k，每次加入一个元素后，如果堆的大小超过 k，就弹出堆顶元素。
解释一下堆，就是完全二叉树，每个节点的左右子树都是堆，且根节点是堆顶。
小顶堆的性质是，堆顶元素是堆中最小的元素。
大顶堆的性质是，堆顶元素是堆中最大的元素。