代码随想录day13 ● 150. 逆波兰表达式求值 ● 239. 滑动窗口最大值 ● 347.前 K 个高频元素

150. 逆波兰表达式求值

解题步骤：

第一步：创建一个栈；

第二步：遍历整个数组；

第三步：判断遍历到的元素是运算符还是数字；

　　数字：直接压入栈中

　　运算符：将栈顶两个元素做相应运算后再压入栈中

第四步：弹出栈顶元素。

 1 class Solution {
 2 public:
 3     int evalRPN(vector<string>& tokens) {
 4         stack<int> st;
 5         for (int i = 0; i < tokens.size(); i++){
 6             if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){
 7                 //去除栈顶的两个元素
 8                 int num1 = st.top();
 9                 st.pop();
10                 int num2 = st.top();
11                 st.pop();
12                 //判断运算符号
13                 if (tokens[i] == "+") st.push(num2 + num1);
14                 if (tokens[i] == "-") st.push(num2 - num1);
15                 if (tokens[i] == "*") st.push(num2 * num1);
16                 if (tokens[i] == "/") st.push(num2 / num1);
17             } else {
18                 st.push(stoi(tokens[i]));
19             }
20         }
21         int result = st.top();
22         return result;
23     }
24 };

*239. 滑动窗口最大值

 1 class Solution {
 2 private:
 3     class MyQueue{
 4     public:
 5         //使用deque来实现单调队列
 6         deque<int> que;
 7         //每次弹出的时候，判断当前的弹出的数值是否等于队列出口的元素，如果相等则弹出
 8         //每次弹出前判断队列是否为空
 9         void pop(int value){
10             if (!que.empty() && value == que.front()){
11                 que.pop_front();
12             }
13         }
14         //如果push的数值大于后端元素的数值，那么就将后端的数值弹出，直到push的数值小于队列入口的元素为止
15         //这样就保证了队列里的数值是单调从大到小的了
16         void push(int value){
17             while (!que.empty() && value > que.back()){
18                 que.pop_back();
19             }
20             que.push_back(value);
21         }
22         //查询当前队列最大值
23         int front(){
24             return que.front();
25         }
26     };
27 public:
28     vector<int> maxSlidingWindow(vector<int>& nums, int k) {
29         MyQueue que;
30         vector<int> result;
31         for (int i = 0; i < k; i++){//先将前k元素放进队列
32             que.push(nums[i]);
33         }
34         result.push_back(que.front());
35         for (int i = k; i < nums.size(); i++){
36             //滑动窗口移除最前面的元素
37             que.pop(nums[i - k]);
38             //滑动窗口加入最后面的元素
39             que.push(nums[i]);
40             //记录对应的最大值
41             result.push_back(que.front());
42         }
43         return result;
44     }
45 };

*347. 前 K 个高频元素

 1 class Solution {
 2 public:
 3     // 小顶堆
 4     class mycomparison {
 5     public:
 6         bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
 7             return lhs.second > rhs.second;
 8         }
 9     };
10     vector<int> topKFrequent(vector<int>& nums, int k) {
11         // 要统计元素出现频率
12         unordered_map<int, int> map; // map<nums[i],对应出现的次数>
13         for (int i = 0; i < nums.size(); i++) {
14             map[nums[i]]++;
15         }
16 
17         // 对频率排序
18         // 定义一个小顶堆，大小为k
19         priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
20 
21         // 用固定大小为k的小顶堆，扫面所有频率的数值
22         for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
23             pri_que.push(*it);
24             if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
25                 pri_que.pop();
26             }
27         }
28 
29         // 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
30         vector<int> result(k);
31         for (int i = k - 1; i >= 0; i--) {
32             result[i] = pri_que.top().first;
33             pri_que.pop();
34         }
35         return result;
36 
37     }
38 };