主題
題目連結：
題目意譯：
請設計一個類堆疊的資料結構，其可以將元素推入到堆疊中並將出現最頻繁的元素移出堆疊中。
實作類別 FreqStack：
FreqStack() 建立一個空的頻率堆疊（Frequency Stack）。
void push(int val) 將一整數 val 放入堆疊的頂端。
int pop() 將堆疊中出現頻率最高的算移除並回傳。
如果有多個出現頻率最高的元素，則最靠近堆疊頂端的元素將被移除並回傳。
限制：
0 ≦ val ≦ 10 ^ 9
最多 2 × 10 ^ 4 次呼叫是 push 或是 pop。
保證在呼叫 pop 的時候，堆疊中至少有一個元素。
範例測資：
範例 1：
輸入
["FreqStack", "push", "push", "push", "push", "push", "push", "pop", "pop", "pop", "pop"]
[[], [5], [7], [5], [7], [4], [5], [], [], [], []]
輸出
[null, null, null, null, null, null, null, 5, 7, 5, 4]
解釋
FreqStack freqStack = new FreqStack();
freqStack.push(5); // 堆疊為 [5]
freqStack.push(7); // 堆疊為 [5,7]
freqStack.push(5); // 堆疊為 [5,7,5]
freqStack.push(7); // 堆疊為 [5,7,5,7]
freqStack.push(4); // 堆疊為 [5,7,5,7,4]
freqStack.push(5); // 堆疊為 [5,7,5,7,4,5]
freqStack.pop(); // 回傳 5，因為 5 是最頻繁的。堆疊變成 [5,7,5,7,4]。
freqStack.pop(); // 回傳 7，因為 5 和 7 是最頻繁的，但是 7 比較接近堆疊頂端。堆疊變成 [5,7,5,4]。
freqStack.pop(); // 回傳 5，因為 5 是最頻繁的。堆疊變成 [5,7,4]。
freqStack.pop(); // 回傳 4，因為 5 、 4 和 7 是最頻繁的，但是 4 比較接近堆疊頂端。堆疊變成 [5,7]。
解題思維：
以範例測資中的 [5,7,5,7,4,5] 為例：
可以看到如果我們把每個元素都多附加一個新的數值 c，其代表著在該元素之前（含自己）有多少個元素與該元素數值相等（例如第三個 5 的 c 值為 3）。而這用一個雜湊表（Hash Table）便可以輕易地統計任意時刻內堆疊中的各種元素的出現次數，因此在呼叫 push 的時候便可以為每個元素計算其 c 值，而這就是該元素的當前頻率值。
而當我們從堆疊中移除最頻繁的元素 X（例如說上面的陣列中是 5）的時候，並不是把所有與 X 相等的元素移除，而是移除單一一個 X 且其最靠近堆疊頂端。
因此對於其他與 X 相等的元素，上面定義的新數值 c 並不會改變（因為被移除的 X 是出現於這些元素「之後」）。
並且我們可以看到對於單一一種元素而言，它們 c 值將會是遞增的（如果沒有被 pop 的話，單純只有 push）。
而在題目的限制條件中我們可以看到最多會有 20000 次呼叫，因此單一一種元素出現次數最多是 20000。因此我們可以直接開 20000 個堆疊出來，每一個堆疊代表一個頻率值。而我們在 push 新元素的時候，順便按照該元素的 c 值去把該元素複製一份並放入到對應頻率的堆疊中。
在範例中，我們抵達 [5,7,5,7,4,5] 這個狀態的時候，每個頻率值所對應的堆疊內容為以下：
1 次：[5,7,4]
2 次：[5,7]
3 次：[5]
4 次：[]
……
而此時我們肉眼可以看到頻率最大的就是 5（出現了 3 次），所以當呼叫 pop 的時候我們就是將其移除。所以第一次 pop 後各個頻率值對應的堆疊為以下：
1 次：[5,7,4]
2 次：[5,7]
3 次：[]
4 次：[]
……
第二次呼叫 pop 時，可以看到雖然有多個出現次數為 2 次的元素（即 5 和 7）存在，但是因為我們是依照 push 的順序放入各個頻率的堆疊之中。因此此時「2 次」之堆疊頂端的元素 7 會比其左邊的 5 在原本的堆疊中更靠近頂端。因此移除 7 之後，變成：
1 次：[5,7,4]
2 次：[5]
3 次：[]
4 次：[]
……
之後呼叫 pop，也是以此類推。
因此可以看到只要我們知道當前整個堆疊中出現頻率最大值本身是多少（例如說一開始為「3 次」）便可以從對應的堆疊之頂端拿到所求的元素。
而這個「頻序最大值」（以下將其定義為 F，一開始堆疊為空，所以 F = 0）的更新也相當地簡單——在呼叫 push 的時候，如果當前元素的 c 值大於 F，則將 F 更新為 c。
而在呼叫 pop 的時候，每當從 F 這個頻率值對應的堆疊移除所求元素後，如果「F 次」的堆疊空了就表示已經沒有其他元素出現次數 ≧ F 了。而每次移除元素我們只會移除「一個」，因此我們可以斷定下一個最大的頻率值必定為 F - 1，所以我們將 F 更新成 F - 1 即可。
這樣一來就隨時都可以知道當前最大頻率值，便可以找到對應的堆疊並得到所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
