出處： https://leetcode.com/problems/maximum-frequency-stack/
Design a stack-like data structure to push elements to the stack and pop the most frequent element from the stack.
Implement the FreqStack class:
FreqStack()constructs an empty frequency stack.void push(int val)pushes an integervalonto the top of the stack.int pop()removes and returns the most frequent element in the stack.- If there is a tie for the most frequent element, the element closest to the stack’s top 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 FreqStack freqStack = new FreqStack(); freqStack.push(5); // The stack is [5] freqStack.push(7); // The stack is [5,7] freqStack.push(5); // The stack is [5,7,5] freqStack.push(7); // The stack is [5,7,5,7] freqStack.push(4); // The stack is [5,7,5,7,4] freqStack.push(5); // The stack is [5,7,5,7,4,5] freqStack.pop(); // return 5, as 5 is the most frequent. The stack becomes [5,7,5,7,4]. freqStack.pop(); // return 7, as 5 and 7 is the most frequent, but 7 is closest to the top. The stack becomes [5,7,5,4]. freqStack.pop(); // return 5, as 5 is the most frequent. The stack becomes [5,7,4]. freqStack.pop(); // return 4, as 4, 5 and 7 is the most frequent, but 4 is closest to the top. The stack becomes [5,7].
Constraints:
0 <= val <= 109- At most
2 * 104calls will be made topushandpop. - It is guaranteed that there will be at least one element in the stack before calling
pop.
這題考驗 javascript Class 的運用和資料結構的設計，題目要我們在這個 Class 提供兩個方法：
- FreqStack.prototype.push
這個 function 比較單純，就是在增加一個 val 在 data 的最後面 - FreqStack.prototype.pop
刪除出現次數最多次，且排在最後面的 value，並回傳刪除的 value
這邊的資料設計會比較特殊，為了方便取得出現次數最多的結果，我們把資料設計如下：
// 假設我們 push 了 6 次， 分別為 1, 2, 3, 2, 1, 2 。 // 1 出現 2 次， 2 出現一次，那麼資料結構如下 [ empty, [1, 2, 3], [2, 1], [2] ] // 這樣的結構，方便我們在減少資源的消耗下，取得要刪除的目標。
var FreqStack = function() {
this.data = []
this.fmap = new Map()
};
/**
* @param {number} val
* @return {void}
*/
FreqStack.prototype.push = function(val) {
// 出現次數用 Map 來記錄。
const appears = (this.fmap.get(val) || 0) + 1
this.fmap.set(val, appears)
// 利用陣列的 index 當作次數，網上堆疊要 push 的值
if (this.data[appears]) {
this.data[appears].push(val)
} else {
this.data[appears] = [val]
}
};
/**
* @return {number}
*/
FreqStack.prototype.pop = function() {
// 有了上述的資料結構，我們可以很輕鬆地取得要刪除的值。並用 pop 完成刪除的動作
const top = this.data[this.data.length - 1]
const target = top.pop()
// 調整 map 裡面出現的次數。
this.fmap.set(target, this.fmap.get(target) - 1)
// 如果最高次數的陣列是空的，那麼把 data 的最高次數的陣列刪除
if (!top.length) {
this.data.pop()
}
// 回傳被刪除的數字
return target
};
/**
* Your FreqStack object will be instantiated and called as such:
* var obj = new FreqStack()
* obj.push(val)
* var param_2 = obj.pop()
*/
