2

数据结构设计：最大栈

 3 years ago
source link: https://labuladong.github.io/algo/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%B3%BB%E5%88%97/%E6%9C%80%E5%A4%A7%E6%A0%88.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

数据结构设计：最大栈

培养框架思维，真正爱上算法！关注公众号查看更新文章👆

相关推荐：

读完本文，你不仅学会了算法套路，还可以顺便去 LeetCode 上拿下如下题目：

895.最大频率栈（困难）

我个人很喜欢设计特殊数据结构的问题，毕竟在工作中会经常用到基本数据结构，而设计类的问题就非常考验对基本数据结构的理解和运用。

力扣第 895 题要求我们实现一个特殊的数据结构「最大频率栈」，比较有意思，让我们实现下面这两个 API：

class FreqStack {

    // 在栈中加入一个元素 val
    public void push(int val) {}

    // 从栈中删除并返回出现频率最高的元素
    // 如果频率最高的元素不止一个，
    // 则返回最近添加的那个元素
    public int pop() {}
}

比如下面这个例子：

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
// 因为 2 出现了三次

// 栈中元素：[2,7,2,7,4]

stk.pop() // 返回 7
// 2 和 7 都出现了两次，但 7 是最近添加的

// 栈中元素：[2,7,2,4]

stk.pop() // 返回 2

// 栈中元素：[2,7,4]

stk.pop() // 返回 4

// 栈中元素：[2,7]

这种设计数据结构的问题，主要是要搞清楚问题的难点在哪里，然后结合各种基本数据结构的特性，高效实现题目要求的 API。

那么，我们仔细思考一下 push 和 pop 方法，难点如下：

1、每次 pop 时，必须要知道频率最高的元素是什么。

2、如果频率最高的元素有多个，还得知道哪个是最近 push 进来的元素是哪个。

为了实现上述难点，我们要做到以下几点：

1、肯定要有一个变量 maxFreq 记录当前栈中最高的频率是多少。

2、我们得知道一个频率 freq 对应的元素有哪些，且这些元素要有时间顺序。

3、随着 pop 的调用，每个 val 对应的频率会变化，所以还得维持一个映射记录每个 val 对应的 freq。

综上，我们可以先实现 FreqStack 所需的数据结构：

class FreqStack {
    // 记录 FreqStack 中元素的最大频率
    int maxFreq = 0;
    // 记录 FreqStack 中每个 val 对应的出现频率，后文就称为 VF 表
    HashMap<Integer, Integer> valToFreq = new HashMap<>();
    // 记录频率 freq 对应的 val 列表，后文就称为 FV 表
    HashMap<Integer, Stack<Integer>> freqToVals = new HashMap<>();
}

其实这有点类似前文 手把手实现 LFU 算法，注意 freqToVals 中 val 列表用一个栈实现，如果一个 freq 对应的元素有多个，根据栈的特点，可以首先取出最近添加的元素。

要记住在 push 和 pop 方法中同时修改 maxFreq、VF 表、FV 表，否则容易出现 bug。

现在，我们可以来实现 push 方法了：

public void push(int val) {
    // 修改 VF 表：val 对应的 freq 加一
    int freq = valToFreq.getOrDefault(val, 0) + 1;
    valToFreq.put(val, freq);
    // 修改 FV 表：在 freq 对应的列表加上 val
    freqToVals.putIfAbsent(freq, new Stack<>());
    freqToVals.get(freq).push(val);
    // 更新 maxFreq
    maxFreq = Math.max(maxFreq, freq);
}

pop 方法的实现也非常简单：

public int pop() {
    // 修改 FV 表：pop 出一个 maxFreq 对应的元素 v
    Stack<Integer> vals = freqToVals.get(maxFreq);
    int v = vals.pop();
    // 修改 VF 表：v 对应的 freq 减一
    int freq = valToFreq.get(v) - 1;
    valToFreq.put(v, freq);
    // 更新 maxFreq
    if (vals.isEmpty()) {
        // 如果 maxFreq 对应的元素空了
        maxFreq--;
    }
    return v;
}

这样，两个 API 都实现了，算法执行过程如下：

嗯，这道题就解决了，Hard 难度的题目也不过如此嘛~

以往的数据结构设计文章：

＿＿＿＿＿＿＿＿＿＿＿＿＿

《labuladong 的算法小抄》已经出版，关注公众号「labuladong」查看详情；后台回复关键词「进群」可加入算法群，大家一起刷题/内推：

Copyright © labuladong 2020 all right reserved，powered by Gitbook该文件修订时间： 2021-04-19 18:19:19

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK