文章目录

• 栈与队列
• • 6. 逆波兰表达式求值
  • 7. 滑动窗口最大值
  • 8. 前 K 个高频元素

栈与队列

6. 逆波兰表达式求值

150. 逆波兰表达式求值

思路：
遇到数字压栈，遇到符号弹出两个数做运算，算完的结果放回栈中。

class Solution {
public:int evalRPN(vector& tokens) {stack stk;int num1, ans;for (string s : tokens) {if ( s.length() > 1 || (s[0] <= '9' && s[0] >= '0') ) {stk.push(stoi(s));} else {char ch = s[0];switch(ch) {case '+':num1 = stk.top(); stk.pop();ans = stk.top() + num1; stk.pop();break;case '-':num1 = stk.top(); stk.pop();ans = stk.top() - num1; stk.pop();break;case '*':num1 = stk.top(); stk.pop();ans = stk.top() * num1; stk.pop();break;case '/':num1 = stk.top(); stk.pop();ans = stk.top() / num1; stk.pop();break;default:break;}stk.push(ans);}}return stk.top();}
};

7. 滑动窗口最大值

239. 滑动窗口最大值

思路：
经典的单调队列：
维护队列中是窗口内的单调不增序列。
队首维护的是窗口内的最大值，当一个元素要压入时，判断其是否小于队尾元素，不满足则将队尾比其小的元素全部弹出，再压入该元素。
一个元素何时退出单调队列？当该元素退出滑动窗口时，从队首取走当前元素（若不在则不需要考虑）。

class Solution {
private:class MyQueue {public:deque que;void pop(int num) {if (!que.empty() && num == que.front()) {que.pop_front();}}void push(int num) {while (!que.empty() && num > que.back()) {que.pop_back();}que.push_back(num);}int front() {return que.front();}};public:vector maxSlidingWindow(vector& nums, int k) {MyQueue que;vector 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;}
};

8. 前 K 个高频元素

347. 前 K 个高频元素

思路：

1. 统计每个数字出现的次数
2. 维护一个有 k 个值得小根堆（堆中存放数值，排序依据是数值出现次数）
3. 超过 k 个值时，将堆顶（即堆中出现次数最少的元素）弹出，压入新的值，最后剩下的 k 个数值就是出现次数最大的 k 个数值。
   利用数据结构 优先队列 实现小顶堆。

class Solution {
public:class mycmp {public:bool operator()(const pair& lhs, const pair& rhs) {return lhs.second > rhs.second; // 小根堆}};vector topKFrequent(vector& nums, int k) {vector result(k);unordered_map mp;for (int num : nums) {mp[num]++;}priority_queue, vector>, mycmp> pri_que;for (unordered_map::iterator it = mp.begin(); it != mp.end(); it++) {pri_que.push(*it);if (pri_que.size() > k) {pri_que.pop();}}for (int i = k - 1; i >= 0; i--) {result[i] = pri_que.top().first;pri_que.pop();}return result;}
};