2020年6月16日 星期二

Leetcode題解 Python：Maximum Frequency Stack

實作一個 FreqStack，類似 stack，但 pop() 會先從出現次數最高的最後一個開始，也就是 出現次數 > 位置 的順序。

這題導入了 Freq 的計數，因此要有一個計數的設計，用一個 HashTable 去記錄 val 對應的出現次數。

接下來要把 stack 套上以計數為優先的方式，出現最多次的一定先被 pop() 掉，對相同次數的來說，pop() 是正常的。
但對不同次數的來說，一定要先 pop() 光更多次的，才會輪到自己這一層。

如果連 push 五次同一個 val，那麼會是第五次的 val 先被 pop() ，才會換到第四次的 val，中間會有個換層的移動，如果已經pop()光就往下一層。
fruq = {1:[val], 2:[val], 3:[val], 4:[val], 5:[val]}

在計數的時候，各 val 計數的最高值也就是最優先要被 pop() 的那一層，用一個 MaxFreq 去記錄。
fruq[MaxFreq].pop() 過後，fruq[MaxFreq] == [] 時， MaxFreq -= 1 ，同時也要把 count[val] -= 1。

雖然標 hard，但非常快就解出了，感覺要定為 medium。不過結果我寫的跟官方的只有變數命名有差。

Python 
class FreqStack:

    def __init__(self):
        self.count = defaultdict(int)
        self.freq = defaultdict(list)
        self.MaxFreq = 0

    def push(self, x: int) -> None:
        self.count[x] += 1
        self.freq[self.count[x]].append(x)
        self.MaxFreq = max(self.MaxFreq, self.count[x])

    def pop(self) -> int:
        num = self.freq[self.MaxFreq].pop()        
        self.count[num] -= 1
        if not self.freq[self.MaxFreq]: self.MaxFreq -= 1
        return num
於
標籤： ,