欣迪

出處: 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 integer val onto 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 * 104 calls will be made to push and pop.
  • 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()
 */

訂閱 IT-Monk

訂閱最新文章的發布消息! 😚😚😚
Loading

作者介紹 - 欣迪

欣迪

從設計到寫程式,發現自己有追求前端技巧的自虐傾向。不斷的踩坑,再從坑裡爬出來,慢慢對攀岩有點心得。 目前在多間公司擔任網站設計顧問。 同時也是網站架設公司負責人。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。