LeetCode: 895. Maximum Frequency Stack

题目描述

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:

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.

解题思路

用 map 记录下出现次数和出现该次数的数字出现的顺序的堆栈，然后根据记录的最大出现次数做 push 和 pop 操作。

AC 代码

class FreqStack {
public:
    FreqStack() {
        m_maxFreq = 0;
    }

    void push(int x) {
        ++m_num2Times[x];
        if(m_num2Times[x] > m_maxFreq)
        {
            m_maxFreq = m_num2Times[x];
        }

        // 将 x 加入其对应出现次数的堆栈中
        m_times2Stk[m_num2Times[x]].push(x);
    }

    int pop() {
        int ans = m_times2Stk[m_maxFreq].top();
        --m_num2Times[ans];
        m_times2Stk[m_maxFreq].pop();

        if(m_times2Stk[m_maxFreq].empty()) --m_maxFreq;

        return ans;
    }
private:
    // 数字出现次数及其对应数字的栈的映射，
    // m_times2Stk[i]栈内记录的是出现 i 次数字出现的顺序
    map<int, stack<int>> m_times2Stk; 
    // 数字及其出现次数的映射
    map<int, int> m_num2Times;       
    // 出现次数最多的数字出现的次数
    int m_maxFreq;
};

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