leetcode/problems-cpp/maximum-frequency-stack/solution.h at main · goodstudyqaq/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

typedef array<int, 3> a3;
class FreqStack {
   public:
    vector<stack<int>> V;
    unordered_map<int, int> M;

    FreqStack() {
        V.push_back(stack<int>{});
        V.push_back(stack<int>{});
    }
    void push(int val) {
        debug("push", val);
        if (M.count(val)) {
            M[val]++;
            int cnt = M[val];
            if (cnt < V.size()) {
                V[cnt].push(val);
            } else {
                stack<int> tmp;
                tmp.push(val);
                V.push_back(tmp);
            }
        } else {
            V[1].push(val);
            M[val] = 1;
        }
        debug(val, M[val]);
    }

    int pop() {
        debug("pop");
        int res = V.back().top();
        V.back().pop();
        if (V.back().size() == 0) {
            V.pop_back();
        }
        M[res]--;
        if (M[res] == 0) M.erase(res);
        return res;

    }
};

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack* obj = new FreqStack();
 * obj->push(val);
 * int param_2 = obj->pop();
 */