895最大频率栈

一、前言

分类&＃xff1a;Hash Table。

问题来源LeetCode 895 难度&＃xff1a;困难。

问题链接&＃xff1a;https://leetcode-cn.com/problems/maximum-frequency-stack

二、题目

实现 FreqStack&＃xff0c;模拟类似栈的数据结构的操作的一个类。FreqStack 有两个函数&＃xff1a;

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

 示例&＃xff1a;

输入&＃xff1a;
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
输出&＃xff1a;[null,null,null,null,null,null,null,5,7,5,4]
解释&＃xff1a;
执行六次 .push 操作后&＃xff0c;栈自底向上为 [5,7,5,7,4,5]。然后&＃xff1a;pop() -> 返回 5&＃xff0c;因为 5 是出现频率最高的。
栈变成 [5,7,5,7,4]。pop() -> 返回 7&＃xff0c;因为 5 和 7 都是频率最高的&＃xff0c;但 7 最接近栈顶。
栈变成 [5,7,5,4]。pop() -> 返回 5 。
栈变成 [5,7,4]。pop() -> 返回 4 。
栈变成 [5,7]。

提示&＃xff1a;

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

三、思路

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

图解一目了然&＃xff1a;

四、编码实现

//&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
/*
* &＃64;file : 895_FreqStack.h
* &＃64;blogs : https://blog.csdn.net/nie2314550441/article/details/107392902
* &＃64;author : niebingyu
* &＃64;date : 2020/07/16
* &＃64;title : 895.最大频率栈
* &＃64;purpose : 实现 FreqStack&＃xff0c;模拟类似栈的数据结构的操作的一个类。
*
* FreqStack 有两个函数&＃xff1a;
* push(int x)&＃xff0c;将整数 x 推入栈中。
* pop()&＃xff0c;它移除并返回栈中出现最频繁的元素。
* 如果最频繁的元素不只一个&＃xff0c;则移除并返回最接近栈顶的元素。
*
* 示例&＃xff1a;
* 输入&＃xff1a;
* ["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
* [[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
* 输出&＃xff1a;[null,null,null,null,null,null,null,5,7,5,4]
* 解释&＃xff1a;
* 执行六次 .push 操作后&＃xff0c;栈自底向上为 [5,7,5,7,4,5]。然后&＃xff1a;
*
* pop() -> 返回 5&＃xff0c;因为 5 是出现频率最高的。
* 栈变成 [5,7,5,7,4]。
*
* pop() -> 返回 7&＃xff0c;因为 5 和 7 都是频率最高的&＃xff0c;但 7 最接近栈顶。
* 栈变成 [5,7,5,4]。
*
* pop() -> 返回 5 。
* 栈变成 [5,7,4]。
*
* pop() -> 返回 4 。
* 栈变成 [5,7]。
*
*
* 来源&＃xff1a;力扣&＃xff08;LeetCode&＃xff09;
* 难度&＃xff1a;困难
* 链接&＃xff1a;https://leetcode-cn.com/problems/maximum-frequency-stack
*/
//&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
#pragma once
#include
#include
#include
#include
using namespace std;#define NAMESPACE_FREQSTACK namespace NAME_FREQSTACK {
#define NAMESPACE_FREQSTACKEND }
NAMESPACE_FREQSTACKclass FreqStack
{
public:unordered_map> ms;unordered_map mi;int maxt;FreqStack(){maxt &＃61; -10;}void push(int x){mi[x]&＃43;&＃43;;ms[mi[x]].push(x);maxt &＃61; max(maxt, mi[x]);}int pop(){int r &＃61; ms[maxt].top();mi[r]--;ms[maxt].pop();if (ms[maxt].empty()) maxt--;return r;}
};以下为测试代码//
// 测试 用例 START
void test(const char* testName, vector> opt, vector expect)
{FreqStack s;vector result;for (auto it : opt){if (it.first &＃61;&＃61; 1) // 入栈s.push(it.second);else if (it.first &＃61;&＃61; 2) // 出栈result.push_back(s.pop());}if (expect &＃61;&＃61; result)cout <}// 测试用例
void Test1()
{vector> opt &＃61;{{1,5},{1,7},{1,5},{1,7},{1,4},{1,5},{2,0},{2,0},{2,0},{2,0}};vector expect &＃61; {5,7,5,4};test("Test1()", opt, expect);
}void Test2()
{vector> opt &＃61;{{1,1},{1,1},{1,1},{1,1},{1,1},{1,9},{1,9},{2,0},{2,0},{2,0},{2,0}};vector expect &＃61; { 1,1,1,9 };test("Test2()", opt, expect);
}NAMESPACE_FREQSTACKEND
// 测试 用例 END
//
void FreqStack_Test()
{NAME_FREQSTACK::Test1();NAME_FREQSTACK::Test2();
}

执行结果&＃xff1a;