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
后缀表达式无需写括号,而中缀表达式需要有括号
栈适用于相邻字符的消除操作
python">class Solution:def evalRPN(self, tokens: List[str]) -> int:# 题目中有个要求:两个整数之间的除法总是 向零截断。向零截断指进行除法运算时,不论结果是正是负,都直接丢掉小数部分,保留整数部分# 但python中的地板除//是取离除法的结果最接近但小于该结果的整数部分# 所以我们要对此题中的除法进行新的定义from operator import add, sub, muldiv = 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
python">from collections import deque
from typing import Listclass 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
python">import heapqclass 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] * kfor 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 提供迭代器来遍历空间么