leetcode 895

问题

Implement FreqStack, a class which simulates the operation of a stack-like data structure.

FreqStack has two functions:

  • push(int x), which pushes an integer x onto the stack.
  • pop() , which removes and returns the most frequent element in the stack. (If there is a tie for most frequent element, the element closest to the top of the stack is removed and returned.)

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Input: 
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
Output: [null,null,null,null,null,null,null,5,7,5,4]
Explanation:
After making six .push operations, the stack is [5,7,5,7,4,5] from bottom to top.  Then:

pop() -> returns 5, as 5 is the most frequent.
The stack becomes [5,7,5,7,4].

pop() -> returns 7, as 5 and 7 is the most frequent, but 7 is closest to the top.
The stack becomes [5,7,5,4].

pop() -> returns 5.
The stack becomes [5,7,4].

pop() -> returns 4.
The stack becomes [5,7].

Note:

  • Calls to FreqStack.push(int x) will be such that 0 <= x <= 10^9.
  • It is guaranteed that FreqStack.pop() won’t be called if the stack has zero elements.
  • The total number of FreqStack.push calls will not exceed 10000 in a single test case.
  • The total number of FreqStack.pop calls will not exceed 10000 in a single test case.
  • The total number of FreqStack.push and FreqStack.pop calls will not exceed 150000 across all test cases.

分析

思路1: 使用set<tuple<int,int,int>> st三元组分别保存频率、最后一个数的时间戳、还有这个数的值。在使用unordered_map <int, stack<int>> mp，保存val依次出现的时间戳。push时，如果该元素出现过，并且还在“栈”中，则将其从st中删除，更新频率、最后一个时间戳之后再插入到st中，同时更新对应的mp。pop时，st中最有一个三元组中的val就是要返回的val，将其从st中删除，同时将val对应的栈的栈顶出栈，最后更新频率、时间戳再插入到st中。push时间复杂度O(logn)，pop时间复杂度O(logn)。

思路2: unordered_map <int, stack<int>>freq 保存每个数出现的频率，unordered_map <int, stack<int>>m 保存每个频率下一次出现的数组。比如一个数val出现了n次，那么val会出现在栈m[1]，m[2]，m[3]...m[n] 中。

代码1

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
// push: O(logn) pop: O(logn)
class FreqStack {
public:
    set<tuple<int,int,int>> st;  // freq, lastTime, val
    unordered_map<int, stack<int>> mp; // val -> times
    int time;
    FreqStack() {
        time = 0;
    }
    void push(int x) {
        int freq, lastTime;
        if (mp.find(x) != mp.end()) {
            freq = mp[x].size();
            lastTime = mp[x].top();
            auto it = st.find(make_tuple(freq, lastTime, x));
            st.erase(it);
        }
        mp[x].push(++time);
        freq = mp[x].size();
        lastTime = time;
        st.insert(make_tuple(freq, lastTime, x));
    }

    int pop() {
        auto it = st.end();
        tuple<int,int,int> t = *(--it);
        int freq     = get<0>(t);
        int lastTime = get<1>(t);
        int val      = get<2>(t);
        st.erase(it);
        mp[val].pop();
        if (mp[val].size() == 0) {
            mp.erase(val);
        } else {
            st.insert(make_tuple(freq-1, mp[val].top(), val));
        }
        return val;
    }
};

代码2

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
// push: O(1) pop: O(1)
class FreqStack {
public:
    unordered_map<int, int> freq;
    unordered_map<int, stack<int>> m;
    // 使用线性表vector<stack<int>> m(10001); 的时候用时会更长一些，
    // 可能是因为这个稀疏性决定的
    int freqMax;
    FreqStack() {
        freqMax = 0;
    }
    
    void push(int x) {
        freq[x]++;
        m[freq[x]].push(x);
        freqMax = max(freqMax, freq[x]);
    }

    int pop() {
        int ret = m[freqMax].top();
        m[freqMax].pop();
        if (m[freqMax].size() == 0)
            freqMax--;
        freq[ret]--;
        return ret;
    }
};