Skip to main content

5-栈和队列

1.栈​

20. 有效的括号​

class Solution {
public:
    bool isValid(string s) {
        if(s.size() % 2 == 1) return false;
        stack<char> st;
        int cur = 0;
        while(cur < s.size())
        {
            if(s[cur] == '(' || s[cur] == '['|| s[cur] == '{') st.push(s[cur]);
            else 
            {
                if(st.empty()) return false;
                int top = st.top();
                st.pop();
                if(s[cur] == ')' && top != '(') return false;
                if(s[cur] == ']' && top != '[') return false;
                if(s[cur] == '}' && top != '{') return false;
            }
            cur++;
        }
        return st.empty();
    }
};

1047. 删除字符串中的所有相邻重复项​

class Solution {
public:
    string removeDuplicates(string s) {
        string res;
        for(auto x : s)
        {
            if(res.size() == 0 || res.back() != x) res.push_back(x);
            else res.pop_back();
        }
        return res;
    }
};

150. 逆波兰表达式求值​

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        vector<int> res;
        int cur = 0;
        while(cur < tokens.size())
        {
            if(tokens[cur] == "+" ||tokens[cur] == "-" ||tokens[cur] == "*" ||tokens[cur] == "/" )
                {
                    int top1 = res.back();
                    res.pop_back();
                    int top2 = res.back();
                    res.pop_back();
                    int r = 0;
                    if(tokens[cur] == "+") r = top2 + top1;
                    if(tokens[cur] == "-") r = top2 - top1;
                    if(tokens[cur] == "*") r = top2 * top1;
                    if(tokens[cur] == "/") r = top2 / top1;
                    res.push_back(r);
                }
            else res.push_back(stoi(tokens[cur]));
            cur++;
        }
        return res.back();
    }
};

71. 简化路径​

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> res;
        stringstream ss(path);
        string s;
        while(getline(ss,s,'/'))
        {
            if(s == ".." && res.size() > 0) res.pop_back();
            else if(s != "" && s != "." && s != "..") res.push_back(s);
        }
        string result;
        for(string x: res)
        {
            result =result +  "/" + x;
        }
        return result == "" ? "/" : result;
    }
};

621. 任务调度器​

class Solution {
public:
    string decodeString(string s) {
        string st;
        stack<int> st_num;
        string res;
        int cur  = 0;

        while(cur < s.size())
        {
            if(s[cur] == ']')
            {
                string tmp;
                while(st.back() != '[')
                {
                    tmp = string(1,st.back()) + tmp;
                    st.pop_back();
                }
                st.pop_back();
                for(int i = 0; i < st_num.top();i++ )
                {
                    st += tmp;
                }
                st_num.pop();
                cur++;
            }
            else if(s[cur] >= '0' && s[cur] <= '9')
            {
                int pre = cur;
                while(s[cur] >= '0' && s[cur] <= '9') cur++;
                st_num.push(stoi(s.substr(pre,cur - pre + 1)));
            }
            else st.push_back(s[cur++]);
        }
        return st;
    }
};

剑指 Offer 31. 栈的压入、弹出序列​

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> st;
        int pushed_start = 0,popped_start = 0;

        while ( popped_start < popped.size())
        {

            if (st.empty() || st.top() != popped[popped_start] )
            {
                if (pushed_start >= pushed.size()) return false;
                st.push(pushed[pushed_start++]);
            }
            else
            {
                st.pop();
                popped_start++;
            }
        }
        return true;
    }
};

1209. 删除字符串中的所有相邻重复项 II​

class Solution {
public:
    string removeDuplicates(string s, int k) {
        string res;
        vector<int> count;
        for(char x : s)
        {
            if(res.size() > 0 && x == res.back())
            {
                if(count.back() + 1 == k)
                {
                    count.pop_back();
                    res.pop_back();
                }
                else
                {
                    int top = count.back();
                    count.pop_back();
                    count.push_back(top + 1);
                }
            }
            else 
            {
                res.push_back(x);
                count.push_back(1);
            }
        }
        string result;
        for(int i = 0; i < res.size();i++)
        {
            result += string(count[i],res[i]);
        }

        return result;
    }
};

32. 最长有效括号​

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        int maxs = 0;
        st.push(-1);
        for(int i = 0; i < s.size();i++)
        {
            if(s[i] == '(') st.push(i);
            else if(!st.empty()) st.pop();
            if(!st.empty()) maxs = max(maxs,i - st.top());
            else st.push(i);
        }
        return maxs;
    }
};

2390. 从字符串中移除星号​

class Solution {
public:
    string removeStars(string s) {
        string res;
        for(char x : s)
        {
            if(x == '*' && res.size()) res.pop_back();
            else res.push_back(x);
        }
        return res;
    }
};

856. 括号的分数***​

class Solution {
public:
    int scoreOfParentheses(string s) {
        stack<int> stk;
        stk.push(0);
        for(char x : s)
        {
            if(x == '(') stk.push(0);
            else
            {
                int t = stk.top();
                stk.pop();
                if(!t) t = 1;
                else t *= 2;
                stk.top() += t;
            }
        }
        return stk.top();
    }
};

678. 有效的括号字符串***​

class Solution {
public:
    bool checkValidString(string s) {
        //维护两个栈，左括号和*栈，优先匹配左括号
        stack<int> left,star;
        for(int i = 0; i < s.size(); ++i) 
        {
            if(s[i] == '(' ) left.push(i);
            else if(s[i] == '*') star.push(i);
            else{
                // 优先与左括号匹配
                if(!left.empty())  left.pop();
                else if(!star.empty()) star.pop();
                else return false;
            }
        }
        //最后如果两个都有值，同时弹出，如果左括号大于*false
        while(!left.empty() && !star.empty())
        {
            int a = left.top(),b = star.top();
            if(a > b) return false;
            left.pop();
            star.pop();
        }
        //如果星号不够返回false
        return left.empty();
    }
};

1190. 反转每对括号间的子串​

class Solution {
public:
    string reverseParentheses(string s) {
        string res;
        for(char x : s)
        {
            if(x == '(' || x != ')') res.push_back(x);
            else
            {
                string temp;
                while(res.back() != '(')
                {
                    temp.push_back(res.back());
                    res.pop_back();
                }
                res.pop_back();
                res = res + temp;
            }
        }
        return res;
    }
};

331. 验证二叉树的前序序列化​

class Solution {
public:
    bool isValidSerialization(string preorder) {
        stringstream ss(preorder);
        //构建一颗二叉树
        vector<string> vec;
        string temp;
        while(getline(ss,temp,',')) vec.push_back(temp);
        stack<int> stk;
        stk.push(1);
        for(string s : vec)
        {
            if(stk.empty()) return false;
            stk.top() -= 1;
            if (stk.top() == 0) {
                stk.pop();
            }
            if(s != "#")stk.push(2);
        }
        return stk.empty();
    }
};

2.队列--堆​

剑指 Offer 59 - II. 队列的最大值​

class MaxQueue {
    deque<int> org;
    deque<int> max_val;
public:
    MaxQueue() {

    }
    
    int max_value() {
        if(max_val.empty()) return -1;
        return max_val.front();
    }
    
    void push_back(int value) {
        org.push_back(value);
        while(!max_val.empty() && max_val.back() < value) max_val.pop_back();
        max_val.push_back(value);
    }
    
    int pop_front() {
        if(org.empty()) return -1;
        int front = org.front();
        if(org.front() == max_val.front()) max_val.pop_front();
        org.pop_front();
        return front;
    }
};

649. Dota2 参议院​

class Solution {
public:
    string predictPartyVictory(string senate) {
        queue<int> r ,d;
        for(int i = 0; i < senate.size();i++)
        {
            if(senate[i] == 'R') r.push(i);
            else d.push(i);
        }
        while(!r.empty() && !d.empty())
        {
            if(r.front() < d.front()) 
            {
                d.pop();
                r.push(r.front() + senate.size());
                r.pop();
            }
            else 
            {
                r.pop();
                d.push(d.front() + senate.size());
                d.pop();
            }
        }
        return r.empty() ?"Dire":"Radiant";
    }
};

622. 设计循环队列​

class MyCircularQueue {
    vector<int> que;
    int head = 0,rear = 0;
public:
    MyCircularQueue(int k): que(k + 1){

    }
    
    bool enQueue(int value) {
        if(isFull()) return false;
        que[rear] = value;
        rear = (rear + 1) % que.size();
        return true;
    }
    
    bool deQueue() {
        if(isEmpty()) return false;
        head = (head + 1) % que.size();
        return true;
    }
    
    int Front() {
        if(isEmpty()) return -1;
        return que[head];
    }
    
    int Rear() {
        if(isEmpty()) return -1;
        return que[(rear + que.size() - 1) % que.size()];
    }
    
    bool isEmpty() {
        return head == rear;
    }
    
    bool isFull() {
        return (rear + 1) % que.size() == head;
    }
};

3.单调栈​

739. 每日温度​

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> st;
        vector<int> res(temperatures.size());
        for(int i = 0; i < temperatures.size();i++)
        {
            while(!st.empty() && temperatures[st.top()] < temperatures[i])
            {
                res[st.top()] = i -  st.top();
                st.pop();
            }
            st.push(i);
        }
        return res;
    }
};

496. 下一个更大元素 I​

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> umap;
        for(int i = 0; i < nums1.size();i++) umap[nums1[i]] = i;
        vector<int> res(nums1.size(),-1);
        stack<int> st;
        for(int i = 0; i < nums2.size();i++) 
        {
            while(!st.empty() && nums2[st.top()] < nums2[i])
            {
                if(umap.find(nums2[st.top()]) != umap.end())
                {
                    res[umap[nums2[st.top()]]] = nums2[i];
                }
                st.pop();
            }
            st.push(i);
        }
        return res;
    }
};

503. 下一个更大元素 II​

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> res(nums.size(),-1);
        stack<int> st;
        for(int i = 0; i < nums.size() * 2;i++) 
        {
            while(!st.empty() && nums[st.top()] < nums[i % nums.size()])
            {
                res[st.top()] = nums[i % nums.size()];
                st.pop();
            }
            st.push(i % nums.size());
        }
        return res;
    }
};

42. 接雨水​

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st;
        int res = 0;
        for(int i = 0; i < height.size();i++)
        {
            if(!st.empty() && height[st.top()] == height[i]) st.pop();
            while(!st.empty() && height[st.top()] < height[i])
            {
                int top = st.top();
                st.pop();
                if(!st.empty())
                {
                    int w = i - st.top() - 1;
                    int h = min(height[i],height[st.top()]) - height[top];
                    res += w*h;
                }
            }
            st.push(i);
        }
        return res;
    }
};

84. 柱状图中最大的矩形​

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        heights.push_back(0);
        heights.insert(heights.begin(),0);
        int res = 0;
        for(int i = 0; i < heights.size();i++)
        {
            if(!st.empty() && heights[st.top()] == heights[i]) st.pop();
            while(!st.empty() && heights[st.top()] > heights[i])
            {
                int top = st.top();
                st.pop();
                if(!st.empty())
                {
                    int w = i - st.top() - 1;
                    int h = heights[top];
                    res = max(w*h , res);
                }
            }
            st.push(i);
        }
        return res;
    }
};

85. 最大矩形​

class Solution {
    int largestRectangleArea(vector<int> heights) {
        stack<int> st;
        heights.push_back(0);
        heights.insert(heights.begin(),0);
        int res = 0;
        for(int i = 0; i < heights.size();i++)
        {
            if(!st.empty() && heights[st.top()] == heights[i]) st.pop();
            while(!st.empty() && heights[st.top()] > heights[i])
            {
                int top = st.top();
                st.pop();
                if(!st.empty())
                {
                    int w = i - st.top() - 1;
                    int h = heights[top];
                    res = max(w*h , res);
                }
            }
            st.push(i);
        }
        return res;
    }
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        //和84题类似
        int res = 0;
        vector<int> heights(matrix[0].size(),0);
        for(int i = 0; i < matrix.size();i++)
        {
            for(int j = 0; j < matrix[0].size();j++)
            {
                if(matrix[i][j] == '1')heights[j] += matrix[i][j] -'0';
                else heights[j] = 0;
            }
            res = max(res,largestRectangleArea(heights));
        }
        return res;
    }
};

155. 最小栈​

class MinStack {
    stack<int>org;
    stack<int>pre;
public:
    MinStack() {

    }
    
    void push(int val) {
        org.push(val);
        if(pre.empty() || pre.top() >= val) pre.push(val);
    } 
    
    void pop() {
        int top = org.top();
        org.pop();
        if(top == pre.top()) pre.pop();
    }
    
    int top() {
        return org.top();
    }
    
    int getMin() {
        return pre.top();
    }
};

剑指 Offer 33. 二叉搜索树的后序遍历序列​

class Solution {
public:
    bool verifyPostorder(vector<int>& postorder) {
        int root = INT_MAX;
        stack<int> st;
        for(int i = postorder.size() - 1; i >= 0 ;i--)
        {
            if(root < postorder[i]) return false;
            while(!st.empty() && st.top() > postorder[i])
            {
                root = st.top();
                st.pop();
            }
            st.push(postorder[i]);
        }
        return true;
    }
};

402. 移掉 K 位数字***​

题解https://leetcode.cn/problems/remove-k-digits/solutions/290203/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-5/

留下数组保持单调递增

class Solution {
public:
    string removeKdigits(string num, int k) {
        if(num.size() <= k) return "0";
        string s;
        int c = k;
        for(int i = 0; i < num.size();i++)
        {
            while(s.size() != 0 && s.back() > num[i]) 
            {
                s.pop_back();
                c--;
                if(c == 0) 
                {
                    s = s + num.substr(i);
                    int pos = std::find_if(s.begin(), s.end(), [](char c) {
                        return c != '0'; }) - s.begin();
                    return s.substr(pos) == "" ? "0" : s.substr(pos);
                }
            }
            s.push_back(num[i]);
        }
        s = s.substr(0,num.size() - k);
        int pos = std::find_if(s.begin(), s.end(), [](char c) {
                        return c != '0'; }) - s.begin();
        return s.substr(pos) == "" ? "0" : s.substr(pos);

    }
};


316. 去除重复字母***（单调栈）​

class Solution {
public:
    string removeDuplicateLetters(string s) {
        unordered_map<char,int> umap; //剩余字符个数
        for(char x : s) umap[x]++;
        string res;
        for(char x : s)
        {
            if(res.find(x) == -1)
            {
                while(!res.empty() && res.back() > x && umap[res.back()] > 0)
                {
                    res.pop_back();
                }
                res.push_back(x);
            }
            umap[x]--;
        }
        return res;
    }
};

907. 子数组的最小值之和***​

维护一个单调递增的栈，弹出时计算贡献度，arr[i] （左边大于它的元素） （右边大于它的元素个数）

class Solution {
    const int MOD = 1e9 + 7;
public:
    int sumSubarrayMins(vector<int> &arr) {
        long ans = 0L;
        arr.push_back(-1);
        stack<int> st;
        st.push(-1); // 哨兵
        for (int r = 0; r < arr.size(); ++r) {
            while (st.size() > 1 && arr[st.top()] >= arr[r]) {
                int i = st.top();
                st.pop();
                ans += (long) arr[i] * (i - st.top()) * (r - i); // 累加贡献
            }
            st.push(r);
        }
        return ans % MOD;
    }
};

456. 132 模式​

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int f = INT_MIN; // f表示 nums[j]，f 有值说明以及弹出了，以及有nums[k]了，此时取最大值就行，后面如果发现有比f小的说明找到了
        stack<int> st;
        for(int i = nums.size() - 1;i >= 0;i--)
        {
            if(f > nums[i]) return true;
            while(!st.empty() && nums[i] > nums[st.top()]) //nums[i] 就是最大元素
            {
                f = max(f,nums[st.top()]);//取最大
                st.pop();
            }
            st.push(i);
        }
        return false;
    }
};

4.单调队列​

239. 滑动窗口最大值（单调队列）​

class Solution {
    //单调队列
    class myQue
    {
    public:
        void push(int val)
        {
            while(!que.empty() && que.back() < val) que.pop_back();
            que.push_back(val);
        }
        void pop(int val)
        {
            if(!que.empty() && que.front() == val) que.pop_front();
        }
        int front()
        {
            return que.front();
        }
 
    private:
        deque<int> que;
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        myQue que;
        for(int i = 0; i < k; i++) que.push(nums[i]);
        res.push_back(que.front());
        for(int i = k; i < nums.size() ; i++)
        {
            que.push(nums[i]);
            que.pop(nums[i-k]);
            res.push_back(que.front());
        }
        return res;
    }
};

1438. 绝对差不超过限制的最长连续子数组***​

class Solution {

public:
    int longestSubarray(vector<int>& nums, int limit) {
        //维护两个单调队列
        deque<int> max_que,min_que;
        int left = 0,right = 0,res = 0;
        while(right < nums.size())
        {
            //max队列进
            while(!max_que.empty() && nums[max_que.back()] < nums[right]) 
            {
                max_que.pop_back();
            }
            //min队列进
            while(!min_que.empty() && nums[min_que.back()] > nums[right]) 
            {
                min_que.pop_back();
            }
            max_que.push_back(right);
            min_que.push_back(right);
            //这里都加进来了 -- 两者最大值和最小值
            while(nums[max_que.front()] - nums[min_que.front()] > limit)
            {
                if(max_que.front() == left) max_que.pop_front();
                else if(min_que.front() == left) min_que.pop_front();
                left++;
            }
            res = max(res,right - left + 1);
            right++;
        }
        return res;
    }
};

5.优先级队列-堆​

692. 前K个高频单词​

class Solution {
    class cmp
    {
        public:
        bool operator()(const pair<string,int> &a ,const pair<string,int> &b)
        {
            if(a.second == b.second) return a.first < b.first;
            return a.second > b.second;
        }
    };
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        priority_queue<pair<string,int>,vector<pair<string,int>>,cmp> que;
        unordered_map<string,int> umap;
        vector<string> res;
        for(auto x: words)  umap[x]++;
        for(auto x: umap)
        {
            que.push(x);
            if(que.size() > k) que.pop();
        }
        while(!que.empty())
        {
            res.push_back(que.top().first);
            que.pop();
        }
        reverse(res.begin(),res.end());
        return res;
    }
};

347. 前 K 个高频元素（堆--优先级队列）​

class Solution {
    class cmp
    {
        public:
        bool operator()(const pair<int,int> &a ,const pair<int,int> &b)
        {
            return a.second > b.second;
        }
    };
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> que;
        unordered_map<int,int> umap;
        vector<int> res;
        for(auto x: nums)  umap[x]++;
        for(auto x: umap)
        {
            que.push(x);
            if(que.size() > k) que.pop();
        }
        while(!que.empty())
        {
            res.push_back(que.top().first);
            que.pop();
        }
        return res;
    }
};

23. 合并 K 个升序链表（堆--优先级队列）​

class Solution {
    class cmp
    {
        public:
        bool operator()(ListNode* a ,ListNode* b)
        {
            return a->val > b->val;
        }
    };
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode*>,cmp> que;
        for(auto x:lists) 
            if(x) que.push(x);
        ListNode* preroot = new ListNode(0);
        ListNode* cur = preroot;
        while(!que.empty())
        {
            ListNode* top = que.top();
            que.pop();
            cur->next = top;
            cur = cur->next;
            top = top->next;
            if(top) que.push(top);
        }
        cur->next =nullptr;
        return preroot->next;
    }
};

LCR 059. 数据流中的第 K 大元素​

class KthLargest {
    priority_queue<int,vector<int>,greater<int>> que;
    int kma;
public:
    KthLargest(int k, vector<int>& nums){
        kma = k;
        for(int x : nums)
        {
            que.push(x);
            if(que.size() > kma) que.pop();
        }
    }
    
    int add(int val) {
        que.push(val);
        if(que.size() > kma) que.pop();
        return que.top();
    }
};

373. 查找和最小的 K 对数字​

class Solution {
public:
  vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        // 最小堆
        auto cmp = [&](const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return nums1[lhs.first] + nums2[lhs.second] > nums1[rhs.first] + nums2[rhs.second];
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> heap(cmp);

        for (int i = 0; i < k && i < nums1.size(); ++i) {
            heap.push({i, 0});
        }
        vector<vector<int>> ret;
        while (k-- > 0 && !heap.empty()) {
            auto ids = heap.top();
            heap.pop();
            ret.push_back({nums1[ids.first], nums2[ids.second]});

            if (ids.second < nums2.size() - 1) {
                heap.push({ids.first, ids.second + 1});
            }
        }

        return ret;
    }
};

215. 数组中的第K个最大元素​

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int,vector<int>,greater<int>> que;
        for(int x : nums)
        {
            que.push(x);
            if(que.size() > k) que.pop();
        }
        return que.top();
    }
};

剑指 Offer 40. 最小的k个数​

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        priority_queue<int,vector<int>> que;
        vector<int> res;
        for(int x : arr)
        {
            que.push(x);
            if(que.size() > k) que.pop();
        }
        while(!que.empty())
        {
            res.push_back(que.top());
            que.pop();
        }
        return res;
    }
};

973. 最接近原点的 K 个点​

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        auto cmp = [&](const vector<int> &a,const vector<int>&b){
            return a[0] * a[0] + a[1] * a[1] < b[0] * b[0] + b[1] * b[1];
        };
        priority_queue<vector<int>,vector<vector<int>>,decltype(cmp)> que(cmp);
        for(auto x : points)
        {
            que.push(x);
            if(que.size() > k) que.pop();
        }
        vector<vector<int>> res;
        while(!que.empty())
        {
            res.push_back(que.top());
            que.pop();
        }
        return res;
    }
};

767. 重构字符串​

class Solution {
    class cmp
    {
        public:
        bool operator()(const pair<char,int> &a ,const pair<char,int> &b)
        {
            return a.second < b.second;
        }
    };
public:
    string reorganizeString(string s) {
        priority_queue<pair<char,int>,vector<pair<char,int>>,cmp> que;
        unordered_map<char,int> umap;
        for(auto x: s)  umap[x]++;
        for(auto x: umap)
        {
            que.push(x);
        }
        string res;
        while(!que.empty())
        {
            pair<char,int> top = que.top();
            que.pop();
            if(res.size() == 0 || res.back() != top.first) 
            {
                res.push_back(top.first);
                if(top.second - 1 > 0) que.push({top.first,top.second - 1});
            }
            else if(res.back() == top.first)
            {
                pair<char,int> top1;
                if(!que.empty()) top1= que.top();
                else return "";
                que.pop();
                res.push_back(top1.first);
                que.push(top);
                if(top1.second - 1 > 0) que.push({top1.first,top1.second - 1});
            }
            
        }
        return res;
    }
};

895. 最大频率栈**​

class FreqStack {
    struct cmp{
        bool operator()(const vector<int> &a,const vector<int> &b)
        {
            if(a[1] == b[1]) return a[2] < b[2];
            return a[1] < b[1];
        }
    };
    //num freq
    unordered_map<int,int> freq;
    //num freq time
    priority_queue<vector<int>,vector<vector<int>>,cmp> que;

    int time = 0;
public:
    FreqStack() {

    }
    
    void push(int val) {
        freq[val]++;
        time++;
        que.push({val,freq[val],time});
    }
    
    int pop() {
        auto x = que.top();
        freq[x[0]]--;
        que.pop();
        return x[0];
    }
};

378. 有序矩阵中第 K 小的元素***​

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        //array<int,3> {值，i，j}
        int n = matrix.size();
        auto cmp = [](const array<int,3> &a,const array<int,3> &b){
            return a[0] > b[0];
        };
        priority_queue<array<int,3>,vector<array<int,3>>,decltype(cmp)> que(cmp);
        //加入 i , 0
        for(int i = 0;i < n;i++) que.push({matrix[i][0],i,0});
        while(k > 1)
        {
            array<int,3> top = que.top();
            que.pop();
            if(top[2] + 1 < n)que.push({matrix[top[1]][top[2] + 1],top[1],top[2] + 1}); 
            k--;
        }

        return que.top()[0];
    }
};

451. 根据字符出现频率排序​

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char,int> umap;
        for(char x : s) umap[x]++;
        string res;
        auto cpm = [&](const pair<char,int> &a,const pair<char,int> &b)
        {
            return a.second < b.second;
        };
        priority_queue<pair<char,int>,vector<pair<char,int>>,decltype(cpm)> que(cpm);

        for(auto x: umap)que.push(x);
        while(!que.empty())
        {
            res += string(que.top().second,que.top().first);
            que.pop();
        }
        return res;
    }
};

1353. 最多可以参加的会议数目​

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        int maxDay = 0;
        // 构建一个【开始天】 和 【结束天】的映射
        unordered_map<int,vector<int>> day2day;
        for(vector<int>& event : events)
        {
            maxDay = max(maxDay , event[1]);
            day2day[event[0]].push_back(event[1]);
        }
        int res = 0;
        priority_queue<int,vector<int>,greater<int>> que;
        for(int i = 1; i <= maxDay;i++)
        {
            // 增加新的结束时间
            if(day2day.count(i) > 0)
            {
                for(int day : day2day[i]) que.push(day);
            }
            // 删除队列里结束时间小于i的会议：因为它们已经结束了，无法再选择
            while(!que.empty() && que.top() < i) que.pop();
            if(!que.empty())  // 直接取最小结束时间会议，次数+1
            {
                que.pop();
                res++;
            }
        }
        return res;
    }
};