LeetCode - 895. Maximum Frequency Stack

tags: LeetCode Guide C++ Hard

原題連結: https://leetcode.com/problems/maximum-frequency-stack/

Difficulty: Hard

題目說明

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.

說明

這題的目標是要實作一個類別，其中有兩個函式需完成:

1. push() -> push一個int到整個stack的頂端
2. pop() -> pop出(並刪除)一個出現次數最多的數中最靠近頂端的值

Code與解析

作法. Stack by Hash [Accept]

Runtime: 264 ms > faster than 29.98%
Memory: 68.2 MB > less than 100.00%

class FreqStack {
    map<int, int> frq; // Frequency of a number
    map<int, vector<int>> lvl; // Record the number that its freq higher than the freq (int).
    int top; // Top of stack, used with lvl.
public:
    FreqStack() {
        frq.clear();
        lvl.clear();
        top = -1;
    }
    
    void push(int x) {
        frq[x]++; // Frquency of a number
        if(frq[x] > top) top = frq[x]; // If freq of a number is highest, update it.
        lvl[frq[x]].push_back(x); // Push the number into the corresponding freq.
    }
    
    int pop() {
        int rtn = lvl[top].back(); // Record the number that should be return.
        lvl[top].pop_back(); // Pop the number.
        frq[rtn]--; // Decrease the freq of the number.
        if(lvl[top].empty()) top--; // If no more number with the freq, decrease the top freq to find most-freq number.
        return rtn;
    }
};

這題的重點在於以下幾點:

1. 要記錄次數
2. 如何找到最靠近末端而最頻繁出現的值

那根據這些考量，我們利用

map<int, int> frq;
第一個int為數字，第二個int為該數字出現的次數

來記錄次數，而實際上的stack部分，則要巧妙的運用到

map<int, vector<int>> lvl;
int為次數，vector<int>為大於此次數的數字

拿Example1舉個例子，在經過前面的push之後，理論上stack會是:

[5, 7, 5, 7, 4, 5]

然而，依據我們儲存的方式，實際上會長成這個樣子:

frq:
[4] -> 1
[5] -> 3
[7] -> 2

lvl: top = 3
[1] -> {5, 7, 4}
[2] -> {5, 7}
[3] -> {5}

這樣有什麼好處呢?我們接著看。如果現在執行了pop()，此時從lvl中來看，最高次數的最末端是5，所以5會被pop掉，那儲存的樣子就會變成:

frq:
[4] -> 1
[5] -> 2
[7] -> 2

lvl: top = 2
[1] -> {5, 7, 4}
[2] -> {5, 7}

一次可能還不明顯，我們再pop一次，這次從lvl中可以發現，最高次數2的那個vector中，存著兩個數，那因為7比較後面，表示7是比較晚被push進來的，所以次數最高且最靠近末端的就會是7，得到以下:

frq:
[4] -> 1
[5] -> 2
[7] -> 1

lvl: top = 2
[1] -> {5, 7, 4}
[2] -> {5}

依此類推。如此一來就能把這題給搞定了！