题目描述：

设计一个支持如下操作的 FreqStack 类：

  • push(int x)：将整数 x 推入栈中。
  • pop()：移除并返回栈中频率最高的元素。如果有多个元素的频率相同，则移除最近推入的那个元素。

要求：

  • 实现 FreqStack 类，支持 push 和 pop 操作。
  • push 和 pop 的操作均在 O(1) 时间复杂度内完成。

示例：

示例 1:

# 输入:
# ["FreqStack","push","push","push","push","pop","push","pop","pop","pop"]
# [[],[5],[7],[5],[7],[],[4],[],[],[]]
# 输出:
# [null,null,null,null,null,7,null,4,5,7]

# 解释:
# FreqStack 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.pop();    // 返回 7, 因为 7 是出现频率最高的元素
# freqStack.push(4);  // 栈变为 [5,7,5,7,4]
# freqStack.pop();    // 返回 4, 因为 4 是最后推入的元素
# freqStack.pop();    // 返回 5, 因为 5 是出现频率最高的元素
# freqStack.pop();    // 返回 7, 因为 7 是最后推入的元素

示例 2:

# 输入:
# ["FreqStack","push","push","pop","pop"]
# [[],[1],[1],[],[]]
# 输出:
# [null,null,null,1,1]

问题分析：

这道题目要求我们实现一个频率栈（FreqStack）。栈中元素有一个频率，每次 pop 操作时需要返回频率最高且最近被推入的元素。如果有多个频率相同的元素，应该返回最近推入的元素。

我们需要解决的关键点是：

  1. 如何在常数时间内找到频率最高的元素。
  2. 如何保持 push 和 pop 操作的高效性。

解决思路：

为了实现高效的 push 和 pop 操作，我们可以使用以下数据结构：

  • 一个哈希表 freq_map 来记录每个元素的频率。
  • 一个哈希表 group_map 来记录每个频率下的元素栈，保证每个频率有一个栈来存储该频率的元素，并且可以按照最新的元素来 pop。

具体做法如下：

  1. push(x)：我们首先更新元素 x 的频率，将 x 放入对应频率的栈中。同时更新 max_freq，即当前栈中频率最大的值。
  2. pop()：从 max_freq 对应的栈中取出栈顶元素，更新频率并减少该频率对应栈的大小。如果 max_freq 对应的栈已经为空，我们需要减少 max_freq。

实现代码：

class FreqStack:

    def __init__(self):
        # 记录每个元素的频率
        self.freq_map = {}
        # 记录每个频率对应的元素栈
        self.group_map = {}
        # 记录最大频率
        self.max_freq = 0

    def push(self, x: int) -> None:
        # 更新元素x的频率
        freq = self.freq_map.get(x, 0) + 1
        self.freq_map[x] = freq
        
        # 更新max_freq
        self.max_freq = max(self.max_freq, freq)

        # 将x加入对应频率的栈中
        if freq not in self.group_map:
            self.group_map[freq] = []
        self.group_map[freq].append(x)

    def pop(self) -> int:
        # 获取max_freq对应的栈顶元素
        top = self.group_map[self.max_freq].pop()
        
        # 更新该元素的频率
        self.freq_map[top] -= 1
        
        # 如果max_freq的栈为空，则将max_freq减小
        if not self.group_map[self.max_freq]:
            self.max_freq -= 1
        
        return top

解释：

  1. __init__：
    • 初始化了 freq_map 来记录每个元素的频率。
    • 初始化了 group_map 来记录每个频率对应的元素栈。
    • 初始化了 max_freq，记录当前频率栈中的最大频率。
  2. push(x)：
    • 更新元素 x 的频率。
    • 更新 max_freq 为当前最大频率。
    • 将元素 x 推入对应频率的栈中。
  3. pop()：
    • 从 max_freq 对应的栈中 pop 出元素。
    • 更新该元素的频率。
    • 如果当前 max_freq 对应的栈为空，将 max_freq 减小。

时间复杂度：

  • push(x)：每次 push 操作都涉及更新 freq_map 和 group_map，这些操作都是常数时间的，所以时间复杂度是 O(1)。
  • pop()：每次 pop 操作涉及从 group_map 中取出栈顶元素，并更新相关的频率，时间复杂度也是 O(1)。

因此，整个实现的时间复杂度对于 push 和 pop 操作都是 O(1)。

测试用例：

# 示例 1
freq_stack = FreqStack()
freq_stack.push(5)  # 栈变为 [5]
freq_stack.push(7)  # 栈变为 [5,7]
freq_stack.push(5)  # 栈变为 [5,7,5]
freq_stack.push(7)  # 栈变为 [5,7,5,7]
print(freq_stack.pop())  # 返回 7
freq_stack.push(4)  # 栈变为 [5,7,5,7,4]
print(freq_stack.pop())  # 返回 4
print(freq_stack.pop())  # 返回 5
print(freq_stack.pop())  # 返回 7

# 示例 2
freq_stack = FreqStack()
freq_stack.push(1)  # 栈变为 [1]
freq_stack.push(1)  # 栈变为 [1, 1]
print(freq_stack.pop())  # 返回 1
print(freq_stack.pop())  # 返回 1

总结

  • 通过使用哈希表记录频率和元素栈，我们能够在常数时间内完成 push 和 pop 操作。
  • max_freq 变量帮助我们快速找到当前频率最高的栈，从而能够高效地执行 pop 操作。