讀完本文，可以去力扣解決如下題目：

895.最大頻率棧（Hard）

我個(gè)人很喜歡設(shè)計(jì)特殊數(shù)據(jù)結(jié)構(gòu)的問(wèn)題，畢竟在工作中會(huì)經(jīng)常用到基本數(shù)據(jù)結(jié)構(gòu)，而設(shè)計(jì)類的問(wèn)題就非常考驗(yàn)對(duì)基本數(shù)據(jù)結(jié)構(gòu)的理解和運(yùn)用。

力扣第 895 題要求我們實(shí)現(xiàn)一個(gè)特殊的數(shù)據(jù)結(jié)構(gòu)「最大頻率棧」，比較有意思，讓我們實(shí)現(xiàn)下面這兩個(gè) API：

class FreqStack {

// 在棧中加入一個(gè)元素 val

public void push（int val） {}

// 從棧中刪除并返回出現(xiàn)頻率最高的元素

// 如果頻率最高的元素不止一個(gè)，

// 則返回最近添加的那個(gè)元素

public int pop（） {}

}

比如下面這個(gè)例子：

FreqStack stk = new FreqStack（）;

// 向最大頻率棧中添加元素

stk.push（2）; stk.push（7）; stk.push（2）;

stk.push（7）; stk.push（2）; stk.push（4）;

// 棧中元素：［2，7，2，7，2，4］

stk.pop（） // 返回 2

// 因?yàn)?2 出現(xiàn)了三次

// 棧中元素：［2，7，2，7，4］

stk.pop（） // 返回 7

// 2 和 7 都出現(xiàn)了兩次，但 7 是最近添加的

// 棧中元素：［2，7，2，4］

stk.pop（） // 返回 2

// 棧中元素：［2，7，4］

stk.pop（） // 返回 4

// 棧中元素：［2，7］

這種設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)的問(wèn)題，主要是要搞清楚問(wèn)題的難點(diǎn)在哪里，然后結(jié)合各種基本數(shù)據(jù)結(jié)構(gòu)的特性，高效實(shí)現(xiàn)題目要求的 API。

那么，我們仔細(xì)思考一下 push 和 pop 方法，難點(diǎn)如下：

1、每次 pop 時(shí)，必須要知道頻率最高的元素是什么。

2、如果頻率最高的元素有多個(gè)，還得知道哪個(gè)是最近 push 進(jìn)來(lái)的元素是哪個(gè)。

為了實(shí)現(xiàn)上述難點(diǎn)，我們要做到以下幾點(diǎn)：

1、肯定要有一個(gè)變量 maxFreq 記錄當(dāng)前棧中最高的頻率是多少。

2、我們得知道一個(gè)頻率 freq 對(duì)應(yīng)的元素有哪些，且這些元素要有時(shí)間順序。

3、隨著 pop 的調(diào)用，每個(gè) val 對(duì)應(yīng)的頻率會(huì)變化，所以還得維持一個(gè)映射記錄每個(gè) val 對(duì)應(yīng)的 freq。

綜上，我們可以先實(shí)現(xiàn) FreqStack 所需的數(shù)據(jù)結(jié)構(gòu)：

class FreqStack {

// 記錄 FreqStack 中元素的最大頻率

int maxFreq = 0;

// 記錄 FreqStack 中每個(gè) val 對(duì)應(yīng)的出現(xiàn)頻率，后文就稱為 VF 表

HashMap《Integer， Integer》 valToFreq = new HashMap《》（）;

// 記錄頻率 freq 對(duì)應(yīng)的 val 列表，后文就稱為 FV 表

HashMap《Integer， Stack《Integer》》 freqToVals = new HashMap《》（）;

}

其實(shí)這有點(diǎn)類似前文 手把手實(shí)現(xiàn) LFU 算法，注意 freqToVals 中 val 列表用一個(gè)棧實(shí)現(xiàn)，如果一個(gè) freq 對(duì)應(yīng)的元素有多個(gè)，根據(jù)棧的特點(diǎn)，可以首先取出最近添加的元素。

要記住在 push 和 pop 方法中同時(shí)修改 maxFreq、VF 表、FV 表，否則容易出現(xiàn) bug。

現(xiàn)在，我們可以來(lái)實(shí)現(xiàn) push 方法了：

public void push（int val） {

// 修改 VF 表：val 對(duì)應(yīng)的 freq 加一

int freq = valToFreq.getOrDefault（val， 0） + 1;

valToFreq.put（val， freq）;

// 修改 FV 表：在 freq 對(duì)應(yīng)的列表加上 val

freqToVals.putIfAbsent（freq， new Stack《》（））;

freqToVals.get（freq）.push（val）;

// 更新 maxFreq

maxFreq = Math.max（maxFreq， freq）;

}

pop 方法的實(shí)現(xiàn)也非常簡(jiǎn)單：

public int pop（） {

// 修改 FV 表：pop 出一個(gè) maxFreq 對(duì)應(yīng)的元素 v

Stack《Integer》 vals = freqToVals.get（maxFreq）;

int v = vals.pop（）;

// 修改 VF 表：v 對(duì)應(yīng)的 freq 減一

int freq = valToFreq.get（v） - 1;

valToFreq.put（v， freq）;

// 更新 maxFreq

if （vals.isEmpty（）） {

// 如果 maxFreq 對(duì)應(yīng)的元素空了

maxFreq--;

}

return v;

}

這樣，兩個(gè) API 都實(shí)現(xiàn)了，算法執(zhí)行過(guò)程如下：

嗯，這道題就解決了，Hard 難度的題目也不過(guò)如此嘛~

原文標(biāo)題：數(shù)據(jù)結(jié)構(gòu)基本功：設(shè)計(jì)最大頻率棧

文章出處：【微信公眾號(hào)：算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。

責(zé)任編輯：haq