任务
150. 逆波兰表达式求值
思路
用栈保存操作数，遇到操作符，将操作数弹出并处理。注意除法的逻辑
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
s = []
from operator import add, sub, mul
op_dic = {'+':add,'-':sub }
for i in range(len(tokens)):
if tokens[i] not in {'+','-','*','/'}:
s.append(int(tokens[i]))
elif tokens[i] == '+':
op2 = s.pop()
op1 = s.pop()
s.append(add(op1,op2))
elif tokens[i] == '-':
op2 = s.pop()
op1 = s.pop()
s.append(sub(op1,op2))
elif tokens[i] == '*':
op2 = s.pop()
op1 = s.pop()
s.append(mul(op1,op2))
elif tokens[i] == '/':
op2 = s.pop()
op1 = s.pop()
val = op1//op2 if op1 * op2 > 0 else -(abs(op1) // abs(op2))# 向0取整
s.append(val)
return s[0]
239. 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值
思路
额外维护这样一个滑动窗口（双端队列结构），因此该结构需要保证：某一时刻，双端队列中头结点的值为最大值。
逻辑上，双端队列维护的是什么信息呢？
- 如果依次扩充窗口，谁会成为最大值的信息。
- 如果不再扩充而是依次缩减滑动窗口，谁会成为最大值的信息。
当数组中的窗口往右扩时，为了维护上述结构，需要队列中将它之前比它小的数都移除出去。这个是比较好想到的。
更深入的思考：为什么新的数进来后可以让之前比它小的数（或者相等的数）弹出呢？因为这个弹出的数再也不可能成为最大值了，我的新数比你大还比你晚过期，那么就不需要你这个旧的小值了。也即是，滑动窗口实际上维护的信息是两个维度，数字越新越大越优先。按照上述逻辑，实际上，双端队列每一时刻都是单调递减的。那么缩减呢？只有当前要缩减的元素没有在之前扩充时处理过，才缩减，否则已经被处理过了。
完整的算法如下
- 扩充：只要比当前要入队的数小,则从窗口中弹出
- 缩减：如果和头节点的数一样（旧的最大值），则弹出。否则当前需要处理的数就是又旧又不是之前的最大值的数，扩充时已经被处理过了。
- 最大值：队首元素
class MyWindow:
def __init__(self):
self.queue = deque()
def push(self,val):
while(self.queue and val > self.queue[-1]): #只要比当前要入队的数小,则从窗口中弹出
self.queue.pop()
self.queue.append(val) #将当前值放入滑动窗口
def pop(self,val):
if(self.queue and self.queue[0] == val):
self.queue.popleft()
def getMaxValue(self)->int:
return self.queue[0]
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
res = []
window = MyWindow()
for i in range(k):
window.push(nums[i])
res.append(window.getMaxValue())
size = len(nums)
for i in range(k,size):
window.pop(nums[i-k])
window.push(nums[i])
maxV = window.getMaxValue()
res.append(maxV)
return res
347.前 K 个高频元素
思路
堆（优先级队列）
这里只考虑优先级队列的功能，暂时不考虑实现（上滤下滤等），以小顶堆为例，即在加入和删除元素的过程中，堆顶元素保持最小值。
我们用dic来统计频率，然后利用小顶堆依次添加，达到k个后，再依次添加和弹出最小元素，保证最大的k个元素均在小顶堆中，即可完成。
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
import heapq
import collections
dic = collections.defaultdict(int)
for i in range(len(nums)):
dic[nums[i]] += 1
pq = [] #默认小顶堆
for key,v in dic.items():
heapq.heappush(pq,(v,key))
if len(pq) > k: #后续每次新加入元素，满足堆的结构后，弹出堆顶元素（最小值）
heapq.heappop(pq)
#此时pq中的元素为最大的k个元素,pq的堆顶为这k个内最小的元素
res = [0]*k
for i in range(k-1,-1,-1): #逆序赋值，保证次数单调递减，val的次数越多的越靠前
val = heapq.heappop(pq)[1]
res[i] = val
return res
心得体会
复习了栈的应用，学习了滑动窗口（双端队列）和优先级队列。注意后两种结构的思路和应用。
- 栈的应用 相邻项之间的消除
- 滑动窗口 与之前的数组中那道题不同，本题是自定义了一种特殊功能的数据结构，保证了可以很快取出极值，并随着窗口的滑动，这个性质保持不变。
- 优先级队列 同样利用元素的插入删除，堆结构性质的一致性，保证栈顶为极值，解决topK问题。