895最大频率栈

水深无声 2023-02-27 08:27 46阅读 0赞

## 一、前言 ##

分类：Hash Table。

问题来源LeetCode 895 难度：困难。

问题链接：[https://leetcode-cn.com/problems/maximum-frequency-stack][https_leetcode-cn.com_problems_maximum-frequency-stack]

## 二、题目 ##

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

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

**示例：**

输入：
    ["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]。

**提示：**

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

## 三、思路 ##

本题中我们关注的是出现的频率和入栈顺序。

**图解一目了然：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70][]

## 四、编码实现 ##

//==========================================================================
    /*
    * @file    : 895_FreqStack.h
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/107392902
    * @author  : niebingyu
    * @date    : 2020/07/16
    * @title   : 895.最大频率栈
    * @purpose : 实现 FreqStack，模拟类似栈的数据结构的操作的一个类。
    *
    * FreqStack 有两个函数：
    * push(int x)，将整数 x 推入栈中。
    * pop()，它移除并返回栈中出现最频繁的元素。
    * 如果最频繁的元素不只一个，则移除并返回最接近栈顶的元素。
    *
    * 示例：
    * 输入：
    * ["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]。
    *
    *
    * 来源：力扣（LeetCode）
    * 难度：困难
    * 链接：https://leetcode-cn.com/problems/maximum-frequency-stack
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <stack>
    #include <unordered_map>
    #include <algorithm>
    using namespace std;
    
    #define NAMESPACE_FREQSTACK namespace NAME_FREQSTACK {
    #define NAMESPACE_FREQSTACKEND }
    NAMESPACE_FREQSTACK
    
    class FreqStack
    {
    public:
        unordered_map<int, stack<int>> ms;
        unordered_map<int, int> mi;
        int maxt;
        FreqStack()
        {
            maxt = -10;
        }
    
        void push(int x)
        {
            mi[x]++;
            ms[mi[x]].push(x);
            maxt = max(maxt, mi[x]);
        }
    
        int pop()
        {
            int r = ms[maxt].top();
            mi[r]--;
            ms[maxt].pop();
            if (ms[maxt].empty()) 
                maxt--;
    
            return r;
        }
    };
    
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, vector<pair<int,int>> opt, vector<int> expect)
    {
        FreqStack s;
        vector<int> result;
        for (auto it : opt)
        {
            if (it.first == 1) // 入栈
                s.push(it.second);
            else if (it.first == 2) // 出栈
                result.push_back(s.pop());
        }
    
        if (expect == result)
            cout << testName << ", solution passed." << endl;
        else
            cout << testName << ", solution failed. " << endl;
    }
    
    // 测试用例
    void Test1()
    {
        vector<pair<int, int>> opt =
        {
            {1,5},{1,7},{1,5},{1,7},{1,4},{1,5},
            {2,0},{2,0},{2,0},{2,0}
        };
    
        vector<int> expect = {5,7,5,4};
        test("Test1()", opt, expect);
    }
    
    void Test2()
    {
        vector<pair<int, int>> opt =
        {
            {1,1},{1,1},{1,1},{1,1},{1,1},{1,9},{1,9},
            {2,0},{2,0},{2,0},{2,0}
        };
    
        vector<int> expect = { 1,1,1,9 };
    
        test("Test2()", opt, expect);
    }
    
    NAMESPACE_FREQSTACKEND
    // 测试 用例 END
    //
    void FreqStack_Test()
    {
        NAME_FREQSTACK::Test1();
        NAME_FREQSTACK::Test2();
    }

**执行结果：**

![20200716203334850.png][]

[https_leetcode-cn.com_problems_maximum-frequency-stack]: https://leetcode-cn.com/problems/maximum-frequency-stack
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70]: /images/20230209/53941d95336a494981a6e0e1fbd980c1.png
[20200716203334850.png]: /images/20230209/240de56eba5e4877a18094e897e63a68.png