正文

leetcode0895.最大频率栈(代码片段)

Tisfy  Tisfy  2023-01-06  650

关键词：

【LetMeFly】895.最大频率栈

力扣题目链接：https://leetcode.cn/problems/maximum-frequency-stack/

设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。

实现 FreqStack 类:

FreqStack() 构造一个空的堆栈。
void push(int val) 将一个整数 val 压入栈顶。
int pop() 删除并返回堆栈中出现频率最高的元素。
- 如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。

示例 1：

输入：
["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]
解释：
FreqStack = new FreqStack();
freqStack.push (5);//堆栈为 [5]
freqStack.push (7);//堆栈是 [5,7]
freqStack.push (5);//堆栈是 [5,7,5]
freqStack.push (7);//堆栈是 [5,7,5,7]
freqStack.push (4);//堆栈是 [5,7,5,7,4]
freqStack.push (5);//堆栈是 [5,7,5,7,4,5]
freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,5,7,4]。
freqStack.pop ();//返回 7 ，因为 5 和 7 出现频率最高，但7最接近顶部。堆栈变成 [5,7,5,4]。
freqStack.pop ();//返回 5 ，因为 5 出现频率最高。堆栈变成 [5,7,4]。
freqStack.pop ();//返回 4 ，因为 4, 5 和 7 出现频率最高，但 4 是最接近顶部的。堆栈变成 [5,7]。

提示：

0 <= val <= 10⁹
push 和 pop 的操作数不大于 2 * 10⁴。
输入保证在调用 pop 之前堆栈中至少有一个元素。

方法一：哈希表设计

其实主要也就是两个数据结构，一个是int转int的哈希表，一个是int转stack<int>的哈希表

unordered_map<int, int> value2times记录一个数值出现的次数。假如value2times[1] = 5，那么就说明栈中有5个1
unordered_map<int, stack<int>> times2values记录某个频率的数。假如times2values[3] = [1, 2, 5，那么就说明1、2、5都出现过3次

最后，我们再使用一个整数类型的数据maxTimes来记录整个栈中的“最大频率”

当元素入栈时：

假设入栈了元素val，那么val在栈中出现的次数增加（value2times[val]++）

出现次数增加后，这个元素出现了value2times[val]次（记为thisTimes）

那么我们同时就需要将这个元素插入times2values[thisTimes]这个栈中

最后，更新整个栈中的最大频率maxTimes即可

当元素出栈时：

通过maxTimes我们可以得到栈中元素的“最大出现次数”

因此，value2times[maxTimes]栈的栈顶元素记为要找的元素。（记为value）

将这个元素弹出栈，并将这个元素在栈中的出现次数减一。

如果出栈后maxTimes对应的栈空了，那么就将maxTimes减1

时间复杂度 $O (1)$ ，单次入栈和出栈的时间复杂度都是 $O (1)$
空间复杂度 $O (n)$ ，其中 $n$ 是栈中的最大元素个数

AC代码

C++

class FreqStack 
private:
    unordered_map<int, int> value2times;
    unordered_map<int, stack<int>> times2values;
    int maxTimes;
public:
    FreqStack() 
        maxTimes = 0;
    
    
    void push(int val) 
        value2times[val]++;
        int thisTimes = value2times[val];
        times2values[thisTimes].push(val);
        maxTimes = max(maxTimes, thisTimes);
    
    
    int pop() 
        int value = times2values[maxTimes].top();
        times2values[maxTimes].pop();
        value2times[value]--;
        if (times2values[maxTimes].empty()) 
            maxTimes--;
        
        return value;
    
;

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/128124298

leetcode——最大频率栈(代码片段)

1.题目2.题解维持两个Map+一个变量记录当前最大频率一个Map存储：当前元素——元素频率一个Map存储：频率——频率对应元素（用栈存储）classFreqStackMap<Integer,Integer>freq;//元素——频率Map<Integer,Deque<Integ... 查看详情

leetcode1224最大相等频率[模拟map]heroding的leetcode之路(代码片段)

解题思路：一道标准的模拟题，将满足条件的前缀种类列举下来，有如下四种情况：1111这样只有一类数字的前缀。1234这样每个数字的频率都只有1。1112223334这样一个数字频率为1，其他数字频率相等。111222333444... 查看详情

⭐算法入门⭐《栈-单调栈》困难02——leetcode85.最大矩形(代码片段)

...0c;和我一起打卡！🌞《光天化日学C语言》🌞LeetCode太难？先看简单题！🧡《C语言入门100例》🧡数据结构难？不存在的！🌳《数据查看详情

最大频率栈(代码片段)

最大频率栈设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。实现FreqStack类:FreqStack()构造一个空的堆栈。voidpush(intval)将一个整数val压入栈顶。intpop()删除并返回堆栈中出现频率最高... 查看详情

⭐算法入门⭐《栈-单调栈》困难01——leetcode84.柱状图中最大的矩形(代码片段)

...0c;和我一起打卡！🌞《光天化日学C语言》🌞LeetCode太难？先看简单题！🧡《C语言入门100例》🧡数据结构难？不存在的！🌳《数据查看详情

栈6：最小栈和最大栈3道题(代码片段)

...。我现在找到的有三道：剑指Offer30.包含min函数的栈LeetCode155最小栈LeetCode 716最大栈我们现在就来看一下怎么做。1.剑指查看详情

leetcode单调栈合集(代码片段)

单调栈也是很常见的一种数据结构在刷一些特定的题的时候可以起到很好的效果962最大宽度坡给定一个整数数组A，坡是元组(i,j)，其中i<j且A[i]<=A[j]。这样的坡的宽度为j-i。找出A中的坡的最大宽度，如果不存在... 查看详情

leetcode1224.最大相等频率/1450.在既定时间做作业的学生人数/655.输出二叉树(代码片段)

1224.最大相等频率2022.8.18题目描述给你一个正整数数组nums，请你帮忙从该数组中找出能满足下面要求的最长前缀，并返回该前缀的长度：从前缀中恰好删除一个元素后，剩下每个数字的出现次数都相同。如果删除... 查看详情

leetcode1224.最大相等频率/1450.在既定时间做作业的学生人数/655.输出二叉树(代码片段)

leetcode84.柱状图中最大的矩形(代码片段)

84.柱状图中最大的矩形知识点：单调栈；题目描述给定n个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为1。求在该柱状图中，能够勾勒出来的矩形的最大面积。示例输入：heights=[2,1,5,6,2,3]输出：10... 查看详情

035_最大矩形(代码片段)

知识点：动态规划、单调栈LeetCode第八十五题：https://leetcode-cn.com/problems/maximal-rectangle/submissions/有些题目是真的难，比如这题，答案都不一定抄的明白。语言：GoLang//结合LeetCode84题，逐行计算。抽象问题并结合已有题目的想象力... 查看详情

单调栈应用——矩形最大面积问题(代码片段)

LeetCode84.柱状图中最大的矩形给定n个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为1。求在该柱状图中，能够勾勒出来的矩形的最大面积。输入：heights=[2,1,5,6,2,3]输出：10解释&... 查看详情

单调栈应用——矩形最大面积问题(代码片段)

leetcode1647.minimumdeletionstomakecharacterfrequenciesunique(代码片段)

文章作者：Tyan博客：noahsnail.com | CSDN | 简书1.Description2.Solution**解析：**Version1，先用字典统计每个英文字符出现的频率，然后对频率进行由大到小排序，由大到小排列是因为频率最高的是可以出现的最大... 查看详情

栈最小栈（leetcode155）(代码片段)

...。getMin()——检索栈中的最小元素。来源：力扣（LeetCode）链接：https://leetcode-cn.com 查看详情

[javascript刷题]栈-最小栈,leetcode155(代码片段)

[JavaScript刷题]栈-最小栈,leetcode155githubrepo地址:https://github.com/GoldenaArcher/js_leetcode，Github的目录大概会更新的更勤快一些。题目地址：155.MinStack题目如下：Designastackthatsupportspush,pop,top,andretriev 查看详情

155.最小栈-力扣（leetcode）(代码片段)

目录55.最小栈-力扣（LeetCode）正确题解优化题解1优化题解255.最小栈-力扣（LeetCode）👉155.最小栈-力扣（LeetCode）题目描述：设计push、pop、top、getMin，函数，并且可以在时间复杂度为O(1)的情... 查看详情