Code Exercising Day 10 of “Code Ideas Record“:StackQueue part02

【150. Evaluate Reverse Polish Notation】

Problem Link
Approach: Use a stack. Push numbers onto the stack; when encountering an operator, pop the top two numbers, perform the operation, and push the result back onto the stack.
Helper Function: stoll function: converts a string to a long long type.

class Solution {
public:int evalRPN(vector<string>& tokens) {// LeetCode has modified the backend test data, so long long is neededstack<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]));}}long long result = st.top();st.pop(); // Pop the last element from the stack (though it's not strictly necessary)return result;}
};

【239. Sliding Window Maximum】

Problem Link
Approach: In fact, the queue doesn’t need to maintain all elements within the window. It only needs to maintain elements that could potentially become the maximum in the window, while ensuring the elements in the queue are ordered from largest to smallest.

This type of queue that maintains elements in monotonically decreasing order is called a monotonic queue, i.e., a queue that is either monotonically decreasing or increasing. C++ does not directly support monotonic queues, so we need to implement one ourselves.

Do not assume that implementing a monotonic queue means sorting the numbers within the window. If sorting were involved, how would it differ from a priority queue?

When designing the monotonic queue, the pop and push operations must adhere to the following rules:

1. pop(value): If the element being removed from the window (value) equals the exit element of the monotonic queue, then the queue pops this element. Otherwise, no action is taken.
2. push(value): If the element being pushed (value) is greater than the value of the entry element in the queue, then the entry elements of the queue are popped until the value being pushed is less than or equal to the value of the entry element.
   By adhering to these rules, whenever the window moves, you can simply query que.front() to return the current maximum value in the window.

Using a deque to implement this monotonic queue is most appropriate.
Solution Demo

class Solution {
private:class MyQueue { // Monotonic Queue (decreasing order)public:deque<int> que; // Using deque to implement the monotonic queue// When popping, check if the current value to pop equals the front element of the queue.// Also, check if the queue is currently empty before popping.void pop(int value) {if (!que.empty() && value == que.front()) {que.pop_front();}}// If the value being pushed is greater than the back element of the queue,// pop elements from the back until the pushed value is less than or equal to the back element.// This ensures the queue remains in decreasing order.void push(int value) {while (!que.empty() && value > que.back()) {que.pop_back();}que.push_back(value);}// Query the current maximum in the queue by simply returning the front element.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++) { // First, push the first k elements into the queueque.push(nums[i]);}result.push_back(que.front()); // Record the maximum of the first k elementsfor (int i = k; i < nums.size(); i++) {que.pop(nums[i - k]); // Remove the leftmost element of the sliding windowque.push(nums[i]); // Add the new rightmost element to the sliding windowresult.push_back(que.front()); // Record the corresponding maximum}return result;}
};

【347. Top K Frequent Elements】

Problem Link
Approach: Use a min-heap implemented with a priority queue to sort frequencies (the min-heap is used to exclude the smallest frequencies while maintaining the top K frequencies).
Key Code:

class mycomparison {
public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;// '>' creates a min-heap, opposite to quicksort  }
};priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size() > k) { // If the heap size exceeds K, pop the smallest to maintain size K  pri_que.pop();}
}

class Solution {
public:// Min-heap  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) {// Count element frequencies  unordered_map<int, int> map; // map<nums[i], frequency>  for (int i = 0; i < nums.size(); i++) {map[nums[i]]++;}// Sort frequencies  // Define a min-heap of size k  priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;// Traverse all frequencies with the fixed-size min-heap  for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size() > k) { // If the heap size exceeds K, pop the smallest to maintain size K  pri_que.pop();}}// Extract the top K frequent elements  // Since the min-heap pops the smallest first, reverse the output order  vector<int> result(k);for (int i = k - 1; i >= 0; i--) {result[i] = pri_que.top().first;pri_que.pop();}return result;}
};