LeetCode150. 逆波兰表达式求值
题目链接/文章讲解/视频讲解：https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html
后缀表达式无需写括号，而中缀表达式需要有括号
栈适用于相邻字符的消除操作
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
# 题目中有个要求：两个整数之间的除法总是 向零截断。向零截断指进行除法运算时，不论结果是正是负，都直接丢掉小数部分，保留整数部分
# 但python中的地板除//是取离除法的结果最接近但小于该结果的整数部分
# 所以我们要对此题中的除法进行新的定义
from operator import add, sub, mul
div = lambda x, y: x // y if x * y > 0 else -(abs(x) // abs(y))
opt_fun = {'+' : add, '-' : sub, '*' : mul, '/' : div}
# 用列表模拟栈
stack = []
for i in range(len(tokens)):
# 遇到算符则弹出栈顶的两个数字元素，进行相应的算符运算
if tokens[i] in opt_fun:
num1 = stack.pop()
num2 = stack.pop()
stack.append( opt_fun[ tokens[i] ]( num2 , num1 ) )
# 若遇到数字则压入栈
else:
stack.append( int(tokens[i]) )
ans = stack.pop()
return ans
时间复杂度: O(n)
空间复杂度: O(n)
239. 滑动窗口最大值
本题算比较有难度的，需要自己去构造单调队列
题目链接/文章讲解/视频讲解：https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html
from collections import deque
from typing import List
class Myqueue:
'''
实现单调队列
'''
def __init__(self):
self.que = deque() # 用deque对象模拟单调队列，用list对象会超时
def pop(self, val:int) -> None:
'''
理论上来说滑动窗口每移动一格，需要从单调队列pop一个元素，再push一个元素进入单调队列。
但由于单调队列的对头是当前 滑动窗口中值最大的元素，
所以只有当滑动窗口即将pop的元素等于队头元素时才确确实实需要对单调队列执行pop操作
当滑动窗口即将pop的元素小于队头元素时，说明该元素之前由于小于滑动窗口中最大值而已被pop掉，无需再执行pop操作
'''
if self.que and val == self.que[0]:
self.que.popleft()
def push(self, val:int) -> None:
'''
将即将压入单调队列的元素与队尾元素比大小，若大于队尾元素值，则弹出队尾元素
反复进行上述操作，直到即将压入的的元素小于队尾元素
'''
while self.que and val > self.que[-1]:
self.que.pop()
self.que.append(val)
def getMax(self) -> int:
return self.que[0]
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
que = Myqueue()
result = []
# 先将前k个元素按照单调队列的规则压入队列
for i in range(k):
que.push(nums[i])
tempMax = que.getMax()
result.append(tempMax)
# 滑动窗口开始移动
for i in range( len(nums) - k ):
que.pop( nums[i] )
que.push( nums[i+k])
tempMax = que.getMax()
result.append(tempMax)
return result
时间复杂度: O(n)
空间复杂度: O(k)
347.前 K 个高频元素
大/小顶堆的应用，也即优先级队列
题目链接/文章讲解/视频讲解：https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html
import heapq
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
my_map = {}
# 用哈希表存储nums数组，键为nums中的元素值，key为对应键在nums中出现的次数
for i in range(len(nums)):
my_map[nums[i]] = my_map.get( nums[i], 0 ) + 1 # my_map.get(nums[i],0)指从字典my_map中找出键为nums[i]的value值，若不存在该键，则返回默认值0
# 注：不可用my_map[nums[i]] = my_map[nums[i]] + 1， 因为当my_map中没有mums[i]元素时，无法执行my_map[nums[i]] + 1操作
# 列表用于存储小顶堆
# heapq用于实现逻辑上对堆的各种操作
least_heap = []
# 为什么用小顶堆而不是大顶堆？
# 若用大顶堆，每次往堆中加入新元素并排序后，堆顶元素将是最大的，此时若堆大小大于k，需从堆中推出多余元素，即推出堆顶元素，这样最终在堆中留下来的k个元素将是最小的k个元素，和我们想要的恰恰相反
for value, freq in my_map.items():
# heappush(least_heap, (freq, value))用于将元组(freq, value)插入到堆least_heap中（默认为小顶堆）
# 小顶堆的逻辑是堆顶是最小值，按照元组的第一个元素freq进行排序，若freq相等，则根据元组的第二个元素value进行排序
heapq.heappush( least_heap, (freq, value) )
if len(least_heap) > k:
# heappop()的逻辑是弹出并返回堆顶元素。弹出后，堆结构将自动调整，将最后一个元素移到堆顶，并对其进行下沉操作，确保堆的特性得以恢复
heapq.heappop(least_heap)
#按照出现次数从小到大放入result列表中
result = [0] * k
for i in range(k-1, -1, -1):
result[i] = heapq.heappop(least_heap)[1]
return result
时间复杂度：O(Nlogk)，其中 N 为数组的长度。我们首先遍历原数组，并使用哈希表记录出现次数，每个元素需要 O(1) 的时间，共需 O(N) 的时间。随后，我们遍历「出现次数数组」，由于堆的大小至多为 k，因此每次堆操作需要 O(logk) 的时间，共需 O(Nlogk) 的时间。二者之和为 O(Nlogk)。
空间复杂度：O(N)。哈希表的大小为 O(N)，而堆的大小为 O(k)，共计为 O(N)。
总结
灵魂四问：
- C++中stack，queue 是容器么？
- 我们使用的stack，queue是属于那个版本的STL？
- 我们使用的STL中stack，queue是如何实现的？
- stack，queue 提供迭代器来遍历空间么