哈希算法题目：最大频率栈 题目描述：设计一个类似栈的数据结构，包含以下操作： push(int x)：将整数 x 推入栈中。 pop()：移除并返回栈中出现频率最高的元素。如果频率最高的元素不止一个，则返回最接近栈顶的那个元素。 要求所有操作的时间复杂度为 O(1)。 解题过程循序渐进讲解 步骤1：理解核心需求 我们需要一个栈，但 pop 操作不是简单的后进先出，而是按频率和栈位置双重条件决定。 关键点： 频率最高 ：需要记录每个元素的当前频率。 频率相同 时，选择最接近栈顶的（即最后被 push 的）。 时间复杂度 O(1) 意味着必须用哈希表辅助。 步骤2：数据结构设计 我们需要三个核心组件： 频率表（freq） ：哈希表，记录每个元素当前的频率。 键：元素值（int） 值：当前频率（int） 示例：freq[ 5 ] = 3 表示元素 5 出现了 3 次。 分组栈（group） ：哈希表，以频率为键，存储该频率下的所有元素（按 push 顺序保存）。 键：频率（int） 值：栈（stack）或列表，保存该频率下的元素，最后 push 的在栈顶。 示例：group[ 3] = [ 5, 7 ] 表示频率为 3 的元素有 5 和 7，其中 7 是最后被 push 的。 最大频率（maxFreq） ：记录当前栈中的最高频率，用于快速定位 pop 目标。 步骤3：操作逻辑详解 push(x) 操作： 更新频率：freq[ x ] += 1，得到新频率 f。 更新最大频率：maxFreq = max(maxFreq, f)。 将 x 加入 group[ f] 的栈顶（如果 group[ f ] 不存在则创建新栈）。 示例：依次 push 5, 7, 5, 7, 5 push(5): freq{5:1}, maxFreq=1, group[ 1]=[ 5 ] push(7): freq{5:1,7:1}, maxFreq=1, group[ 1]=[ 5,7 ] push(5): freq{5:2}, maxFreq=2, group[ 2]=[ 5 ] push(7): freq{7:2}, maxFreq=2, group[ 2]=[ 5,7 ] push(5): freq{5:3}, maxFreq=3, group[ 3]=[ 5 ] pop() 操作： 从 group[ maxFreq ] 的栈顶取出元素 x（这就是频率最高且最接近栈顶的元素）。 更新频率：freq[ x ] -= 1。 如果 group[ maxFreq ] 为空，则 maxFreq -= 1（因为最高频率已无元素）。 返回 x。 接上例： pop(): 从 group[ 3] 取 5 → freq[ 5]=2, group[ 3 ] 空，maxFreq=2 → 返回 5 pop(): 从 group[ 2] 取 7 → freq[ 7]=1, group[ 2]=[ 5 ] → 返回 7 pop(): 从 group[ 2] 取 5 → freq[ 5]=1, group[ 2 ] 空，maxFreq=1 → 返回 5 pop(): 从 group[ 1] 取 7 → freq[ 7]=0, group[ 1]=[ 5 ] → 返回 7 pop(): 从 group[ 1 ] 取 5 → 返回 5 步骤4：复杂度分析 push 和 pop 操作只涉及哈希表的增删改查和栈操作，都是 O(1)。 空间复杂度：O(n)，n 为 push 的元素总数。 步骤5：关键技巧总结 用 分组栈 将相同频率的元素按 push 时间排序，保证高频率元素中最后 push 的能被快速访问。 maxFreq 变量避免每次 pop 时遍历所有频率。 频率更新后，旧频率的栈依然保留部分元素（如频率从 3 降到 2，元素仍在 group[ 2 ] 中），这是设计的关键。 通过以上步骤，我们实现了满足要求的最大频率栈。