算法训练营第十一天：逆波兰表达式、滑动窗口最大值与前K个高频元素
150. 逆波兰表达式求值
题目链接：150. 逆波兰表达式求值 - 力扣
解题思路
逆波兰表达式的求值策略相对直接：遍历表达式token列表，当遇到数字时将其压入栈中；遇到运算符时则从栈中弹出两个操作数进行计算，再将结果压回栈中。特别需要关注除法运算的取整规则，当被除数与除数符号相反时，需要采用向上取整的方式处理。
代码实现
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
import math
stack = []
operators = {"+", "-", "*", "/"}
for token in tokens:
if token not in operators:
stack.append(int(token))
else:
b = stack.pop()
a = stack.pop()
if token == "+":
stack.append(a + b)
elif token == "-":
stack.append(a - b)
elif token == "*":
stack.append(a * b)
elif token == "/":
result = a / b
if result < 0:
stack.append(math.ceil(result))
else:
stack.append(math.floor(result))
return stack[0]
239. 滑动窗口最大值
题目链接：239. 滑动窗口最大值 - 力扣
方案一：暴力枚举
最直观的思路是逐个滑动窗口，每次取出窗口内的所有元素并使用Python内置的max函数求最大值，然后将结果加入答案数组。然而这种方法的时间复杂度较高，在数据规模较大时会超出时间限制。
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
res = []
n = len(nums)
for i in range(n - k + 1):
window = nums[i:i+k]
res.append(max(window))
return res
方案二：单调队列优化
采用单调递减队列来维护窗口内的最大值，队列的队首元素始终代表当前窗口的最大值。以示例 nums = [1,3,-1,-3,5,3,6,7], k = 3 为例：
第一轮窗口 [1,3,-1]：依次将1、3入队，由于3大于1，故1出队；-1入队后队列为 [3,-1]，最大值为3
第二轮窗口 [3,-1,-3]：队首3不等于待删除的1，无需操作；-3入队后队列为 [3,-1,-3]，最大值为3
第三轮窗口 [-1,-3,5]：队首3等于待删除的3，需将3出队；5入队时分别与-3、-1比较，两者均出队，最终队列为 [5]，最大值为5
以此类推...
from collections import deque
class MonotonicQueue:
"""单调递减队列"""
def __init__(self):
self.queue = deque()
def pop_element(self, val):
"""当滑窗移出的元素等于队首时，才弹出队首元素"""
if self.queue and val == self.queue[0]:
self.queue.popleft()
def push_element(self, val):
"""入队时保持单调递减，小于当前元素的队尾元素出队"""
while self.queue and val > self.queue[-1]:
self.queue.pop()
self.queue.append(val)
def get_max(self):
return self.queue[0]
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
mq = MonotonicQueue()
result = []
# 初始化第一个窗口
for i in range(k):
mq.push_element(nums[i])
result.append(mq.get_max())
# 滑动窗口
for i in range(k, len(nums)):
mq.pop_element(nums[i - k])
mq.push_element(nums[i])
result.append(mq.get_max())
return result
347. 前 K 个高频元素
题目链接：347. 前 K 个高频元素 - 力扣
解题思路
首先使用哈希表（字典）统计每个元素出现的频率，然后根据频率值进行降序排序，最后取出前k个频率最高的元素即可。
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
from collections import defaultdict
freq_map = defaultdict(int)
for num in nums:
freq_map[num] += 1
# 按频率降序排序
sorted_items = sorted(freq_map.items(), key=lambda x: x[1], reverse=True)
result = []
for num, _ in sorted_items:
result.append(num)
k -= 1
if k == 0:
break
return result
