【设计难题】力扣895-最大频率栈

摘要: 基于链表+哈希表解决与频数相关的设计问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，本文我们来看一个设计问题。需求与频数相关，具体地就是在栈的基础上，push 的操作不变，pop 的操作改为弹出栈中频数最多的元素，如果频数相同，还是弹出最接近栈顶的元素。

在文章 设计-功能系统 中我们系统梳理过设计功能系统的问题。本文解决的问题是一个基于链表+哈希表进行设计的。这种链表+哈希表的设计方法还是比较经典的，在前面的题目汇总中可以找到几个类似的题。此外本题还用到了按照频数对需要维护的信息进行分桶的做法，这也是是个常见操作，lc460、lc1224 等都用到了相同的操作。

---

$1 题目

895. 最大频率栈

实现 FreqStack，模拟类似栈的数据结构的操作的一个类。

FreqStack 有两个函数：

push(int x)，将整数 x 推入栈中。
pop()，它移除并返回栈中出现最频繁的元素。
如果最频繁的元素不只一个，则移除并返回最接近栈顶的元素。

提示：

对 FreqStack.push(int x) 的调用中 0 <= x <= 10^9。
如果栈的元素数目为零，则保证不会调用  FreqStack.pop()。
单个测试样例中，对 FreqStack.push 的总调用次数不会超过 10000。
单个测试样例中，对 FreqStack.pop 的总调用次数不会超过 10000。
所有测试样例中，对 FreqStack.push 和 FreqStack.pop 的总调用次数不会超过 150000。

示例：

输入：
[“FreqStack”,”push”,”push”,”push”,”push”,”push”,”push”,”pop”,”pop”,”pop”,”pop”],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
输出：[null,null,null,null,null,null,null,5,7,5,4]
解释：
执行六次 .push 操作后，栈自底向上为 [5,7,5,7,4,5]。然后：

pop() -> 返回 5，因为 5 是出现频率最高的。
栈变成 [5,7,5,7,4]。

pop() -> 返回 7，因为 5 和 7 都是频率最高的，但 7 最接近栈顶。
栈变成 [5,7,5,4]。

pop() -> 返回 5 。
栈变成 [5,7,4]。

pop() -> 返回 4 。
栈变成 [5,7]。

$2 题解

算法1: 链表+哈希表+频数桶

• list<int> 维护栈的逻辑和元素。
• 频率桶 vector<list<Bag>> 维护特定频数下的各个元素的信息，Bag 是维护一个元素的信息的结构，其信息包括元素值本身，以及它在链表 list<int> 中出现的位置。
• 哈希表联系 list<int> 中的元素和该元素在 vector<list<Bag>> 中的位置。
• 维护全局时间戳，用于对比频率相同时候哪个元素排在前面。

设计细节详见代码中 private 的部分。

代码 (C++)

class FreqStack {
public:
    FreqStack() {
        cnts = vector<list<Bag>>(1);
        stamp = 0;
        st = list<int>();
        mapping = unordered_map<int, list<Bag>::iterator>();
    }

    void push(int x) {
        st.push_back(x);
        list<int>::iterator item_it = --st.end();
        if(mapping.count(x))
        {
            list<Bag>::iterator it = mapping[x];
            int cnt = (it -> items) -> size();
            (it -> items) -> push_front(Item(stamp++, item_it));
            Bag new_item(x, it -> items);
            if((int)cnts.size() == cnt + 1)
                cnts.push_back({});
            cnts[cnt + 1].push_front(new_item);
            cnts[cnt].erase(it);
            mapping[x] = cnts[cnt + 1].begin();
        }
        else
        {
            if((int)cnts.size() == 1)
                cnts.push_back({});
            list<Item> *l = new list<Item>(1, Item(stamp++, item_it));
            cnts[1].push_front(Bag(x, l));
            mapping[x] = cnts[1].begin();
        }
    }

    int pop() {
        int cnt = cnts.size() - 1;
        // 找到待删除元素：删除 st 中最靠近顶的 x
        int x = cnts[cnt].front().x;
        list<int>::iterator item_it = (cnts[cnt].front().items -> front()).it;
        // 创建 new_item 后删除 cnts[cnt].front()
        cnts[cnt].front().items -> pop_front();
        Bag new_item(x, cnts[cnt].front().items);
        cnts[cnt].pop_front();
        if(cnts[cnt].empty())
            cnts.pop_back();
        // 若 cnt -1 >= 1
        // 在 cnts[cnt - 1] 中找到插入 new_item 的位置
        if(cnt >= 2)
        {
            auto it = cnts[cnt - 1].begin();
            while(it != cnts[cnt - 1].end() && (it -> items -> front()).stamp > (new_item.items -> front()).stamp)
                ++it;
            it = cnts[cnt - 1].insert(it, new_item);
            mapping[x] = it;
        }
        else
            mapping.erase(x);
        st.erase(item_it);
        return x;
    }

private:
    struct Item
    {
        int stamp;
        list<int>::iterator it;
        Item(int stamp, list<int>::iterator it):stamp(stamp),it(it){}
    };

    struct Bag
    {
        int x;
        list<Item> *items;
        Bag(int x=-1, list<Item>* items=nullptr):x(x),items(items){}
    };

    int stamp;
    list<int> st;
    unordered_map<int, list<Bag>::iterator> mapping;
    vector<list<Bag>> cnts;
};

算法2: 每个频数维护一个栈

• 哈希表维护元素和元素频数的联系
• 频数桶维护特定频数下的各个元素，用栈维护顺序。桶内的栈只保存使得频数为当前值的那一个元素，例如如果一个元素 x 的频数是 f，则在 1 ~ f-1 的桶中也会有 x 这个元素。

设计细节详见代码中 private 的部分。

代码 (C++)

class FreqStack {
public:
    FreqStack() {
        cnts = vector<stack<int>>(1);
    }

    void push(int x) {
        ++mapping[x];
        int cnt = mapping[x];
        if((int)cnts.size() == cnt)
            cnts.push_back({});
        cnts[cnt].push(x);
    }

    int pop() {
        int cnt = cnts.size() - 1;
        int x = cnts[cnt].top();
        cnts[cnt].pop();
        if(cnts[cnt].empty())
            cnts.pop_back();
        --mapping[x];
        return x;
    }

private:
    vector<stack<int>> cnts;
    unordered_map<int, int> mapping;
};

---