Day11 栈与队列part2
逆波兰表达式求值
150. 逆波兰表达式求值
力扣题目链接(opens new window)
根据 逆波兰表示法，求表达式的值。
有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
- 输入: [“2”, “1”, “+”, “3”, " * "]
- 输出: 9
- 解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
class Solution {
public:int evalRPN(vector<string>& tokens) {stack<long long> st;for(int i = 0; i < tokens.size(); i++){if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){//出现符号，出栈两个元素用于计算long long num1 = st.top();st.pop();long long num2 = st.top();st.pop();// 计算后入栈if (tokens[i] == "+") st.push(num2 + num1);if (tokens[i] == "-") st.push(num2 - num1);if (tokens[i] == "*") st.push(num2 * num1);if (tokens[i] == "/") st.push(num2 / num1);}else{st.push(stoll(tokens[i])); // stoll: str->long long}}return st.top();}
};
import operatorclass Solution:def evalRPN(self, tokens: List[str]) -> int:stack = []ops = {"+": operator.add,"-": operator.sub,"*": operator.mul,"/": lambda a,b : int(a/b)}for token in tokens:if token not in ops:stack.append(int(token))else:b = stack.pop()a = stack.pop()stack.append(ops[token](a, b))return stack.pop()
滑动窗口最大值
239. 滑动窗口最大值
力扣题目链接(opens new window)
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值
这道题不能用优先级队列，大顶堆；因为这个窗口是移动的，而大顶堆每次只能弹出最大值，我们无法移除其他数值，这样就造成大顶堆维护的不是滑动窗口里面的数值了。
class Solution {
private:class MyQueue{public:deque<int> que; // 使用deque来实现单调队列void pop(int value){/*每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。同时pop之前判断队列当前是否为空。假设数组是 [1, 3, 2]，窗口大小 k=2。初始：push(1) → 队列 [1]右移一格：push(3) → 因为 3 > 1，把 1 弹掉，队列 [3]窗口左边的 1 要移出，但它不在队列里了（被挤掉了），所以 pop(1) 什么都不做。下一步：窗口 [3, 2] → push(2) → 队列 [3, 2]现在要移出 3，此时队头就是 3，所以 pop(3) 把它弹掉。这样队列才能始终保持和当前窗口匹配。*/if(!que.empty() && value == que.front()){que.pop_front();}}void push(int value){// 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。// 这样就保持了队列里的数值是单调从大到小的了。while(!que.empty() && value > que.back()){que.pop_back();}que.push_back(value);}int front(){return que.front();}};
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {MyQueue que;vector<int> result;for (int i = 0; i < k; i++){que.push(nums[i]);}result.push_back(que.front());for (int i = k; i < nums.size(); i++){que.pop(nums[i-k]); // 滑动窗口移除最前面元素que.push(nums[i]); // 滑动窗口前加入最后面的元素result.push_back(que.front()); // 记录对应的最大值}return result;}
};
Python 的 collections.deque 是 双端队列（double-ended queue）：
| 方法 | 说明 |
|---|---|
append(x) | 在 右端 加入元素（相当于尾巴） |
appendleft(x) | 在 左端 加入元素（相当于头部） |
pop() | 从右端 弹出元素（尾巴） |
popleft() | 从左端 弹出元素（头部） |
deque 并不是普通队列严格意义上的 FIFO，既可以当队列，也可以当栈来用
from collections import deque
class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:max_list = []kept_nums = deque()for i in range(len(nums)):push_left(kept_nums, nums[i])if i >= k and nums[i-k] == kept_nums[0]:kept_nums.popleft()if i >= k-1: // 最左面的即[0]是最大的max_list.append(kept_nums[0])return max_listdef push_left(kept_nums, num):while kept_nums and num > kept_nums[-1]:kept_nums.pop()kept_nums.append(num)
通过push_left函数我们可以发现，kept_nums相当于c++中的按引用传递了。
Python 没有传统意义上的“按值传递”和“按引用传递”，而是 “对象引用传递”（pass-by-object-reference / pass-by-assignment）。
核心思想
- 传入函数的永远是对象的引用（类似指针）。
- 可变对象（mutable，如 list、dict、set）在函数内被修改，函数外也会看到变化。
- 不可变对象（immutable，如 int、str、tuple）在函数内修改会生成新对象，函数外不会变化。
C++ 有三种常用方式传递：
| 方式 | 函数签名 | 调用方式 | 特点 |
|---|---|---|---|
| 值传递 | void f(int x) | f(a) | 在函数内部复制，修改不影响外部 |
| 指针传递 | void f(int* p) | f(&a) | 函数内部用 *p 修改，外部也会改变；需要手动解引用 |
| 引用传递 | void f(int& x) | f(a) | 函数内部直接用 x 修改，外部也会改变；语法更简洁 |
前 K 个高频元素
347.前 K 个高频元素
力扣题目链接(opens new window)
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
- 输入: nums = [1,1,1,2,2,3], k = 2
- 输出: [1,2]
大/小顶堆的应用， 在C++中就是优先级队列
要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。
class Solution {
public:// 小顶堆class mycomparison {public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}};vector<int> topKFrequent(vector<int>& nums, int k) {// 要统计元素出现频率unordered_map<int, int> map;for (int i = 0; i < nums.size(); i++){map[nums[i]]++;}// 对频率排序// 定义一个小顶堆，大小为kpriority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;// 用固定大小为k的小顶堆，扫面所有频率的数值for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为kpri_que.pop();}}// 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组vector<int> result(k);for (int i = k - 1; i >= 0; i--) {result[i] = pri_que.top().first;pri_que.pop();}return result;}
};
class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:# 使用字典统计数字出现次数time_dict = defaultdict(int)for num in nums:time_dict[num] += 1# 更改字典，key为出现次数，value为相应的数字的集合index_dict = defaultdict(list)for key in time_dict:index_dict[time_dict[key]].append(key)# 排序key = list(index_dict.keys())key.sort() # 升序result = []cnt = 0# 获取前k项while key and cnt <= k:result += index_dict[key[-1]]cnt += len(index_dict[key[-1]])key.pop()return result[0: k]