代码随想录训练营Day09 | 150. 逆波兰表达式求值 - 239. 滑动窗口最大值 - 347.前 K 个高频元素

150. 逆波兰表达式求值

• 题目链接：150. 逆波兰表达式求值
• 思路：本题较为简单，只是使用后缀表达式进行计算没有进行进行中缀表达式到后缀表达式的转换，故使用两个栈，其中一个栈存数字，一个栈存计算符，遇见计算符就将数字栈中的元素pop出两个计算，计算结果push进数字栈，如此重复最终数字栈中的值为最后结果。
• 代码：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;
        int n = tokens.size();
        for (int i = 0; i < n; i++) {
            string& token = tokens[i];
            if (isNumber(token)) {
                stk.push(atoi(token.c_str()));
            } else {
                int num2 = stk.top();
                stk.pop();
                int num1 = stk.top();
                stk.pop();
                switch (token[0]) {
                    case '+':
                        stk.push(num1 + num2);
                        break;
                    case '-':
                        stk.push(num1 - num2);
                        break;
                    case '*':
                        stk.push(num1 * num2);
                        break;
                    case '/':
                        stk.push(num1 / num2);
                        break;
                }
            }
        }
        return stk.top();
    }

    bool isNumber(string& token) {
        return !(token == "+" || token == "-" || token == "*" || token == "/");
    }
};

239. 滑动窗口最大值

• 题目链接：239. 滑动窗口最大值
• 思路：
  1. 暴力法：每次都对遍历滑动窗口所有元素，得到最大值
  2. 单调队列法：使用一个单调队列维护滑动窗口中的元素，从大到小排列。灵神讲单调队列
• 代码：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        int n = nums.size();
        deque<int> q;
        for(int i = 0; i < n; ++i) {
            while(!q.empty() && nums[q.back()] <= nums[i]) {
                q.pop_back(); // 维护单调性
            }
            q.push_back(i);

            if(i - q.front() >= k) // 超出的移除
                q.pop_front();

            if(i >= k - 1)
                ans.push_back(nums[q.front()]); // 每次滑动窗口最大值
            
        }
        return ans;
    }
};

347.前 K 个高频元素

• 题目链接： 347.前 K 个高频元素
• 思路：
  1. 暴力法：遍历数组，统计所有数字次数，对所有数字次数排序，取前K个
  2. 优先队列法：遍历数组，统计所有数字次数，使用优先队列，从大到小排序，维护K个大小即可，优先队列的本质是大顶堆排序，从大到小使用大顶堆排列；
• 代码：

class Solution {
public:
    // 排序法
	vector<int> f1(vector<int>& nums, int k) {
		 vector<int> ans(k, 0);
        unordered_map<int, int> cnt;
        for(int x : nums)
            cnt[x]++;
        vector<pair<int, int>> vec(cnt.begin(), cnt.end());
        ranges::sort(vec, [](pair<int, int> a, pair<int, int> b) {
            return a.second > b.second;
        });

        for(int i = 0; i < k; ++i)
            ans[i] = vec[i].first;
        return ans;
	}
	// 优先队列法
	vector<int> f2(vector<int>& nums, int k) {
		unordered_map<int, int> occurrences;
        vector<int>result;
        for (int v : nums) {
            occurrences[v]++;
        }
        priority_queue<pair<int, int>> q; // 优先队列，内部排列使用的堆排序，默认是大顶堆
        for (const auto& pair : occurrences) {
            q.emplace(pair.second, pair.first); // 第一个值为频率，第二个值为数字
        }
        while(k--){
            result.push_back(q.top().second); // 取前k个
            q.pop();
        }
        return result;
	}
    vector<int> topKFrequent(vector<int>& nums, int k) {
    	return f2(vector<int>& nums, int k);
	}
};