O(1)时间复杂度实现数组getMin()方法（返回最小值后自增）

给定初始有序数组 {1, 2, 3}，需要实现 getMin() 方法，满足以下规则：

• 每次调用方法时，先返回数组当前的最小元素
• 返回后将刚才取出的最小元素的值加1

方法调用的示例流程如下：

getMin(): 返回1，对应最小元素自增1，数组变为 {2, 2, 3}
getMin(): 返回2，对应最小元素自增1，数组变为 {3, 2, 3}
getMin(): 返回2，对应最小元素自增1，数组变为 {3, 3, 3}
getMin(): 返回3，对应最小元素自增1，数组变为 {4, 3, 3}

核心疑问：是否存在时间复杂度为O(1)的解决方案？

存在O(1)均摊时间复杂度的实现方案，核心思路是放弃维护真实的数组结构，改用频次哈希表+单调最小值指针实现，不需要做任何遍历或堆操作。

实现逻辑 #

• 初始化时用哈希表统计数组中每个数值的出现次数，同时记录初始状态下的全局最小值
• 每次调用getMin()时，直接返回当前维护的全局最小值即可，不需要遍历查找
• 返回后将当前最小值的出现频次减1，将「最小值+1」的出现频次加1
• 如果当前最小值的频次已经降到0，说明数组里已经没有这个值了，直接把最小值指针加1即可——因为所有元素的修改都是自增，不可能出现比当前维护的最小值更小的数，最小值指针永远只会单调递增，不需要回溯查找。

代码实现（Python） #

from collections import defaultdict

class MinArray:
    def __init__(self, init_nums):
        self.freq = defaultdict(int)
        self.cur_min = float("inf")
        # 初始化频次和初始最小值
        for num in init_nums:
            self.freq[num] += 1
            if num < self.cur_min:
                self.cur_min = num

    def getMin(self):
        res = self.cur_min
        # 更新频次
        self.freq[res] -= 1
        self.freq[res + 1] += 1
        # 当前最小值耗尽时指针后移
        if self.freq[self.cur_min] == 0:
            self.cur_min += 1
        return res

复杂度验证 #

用初始数组[1,2,3]测试上述代码，连续4次调用getMin()的返回结果依次为1、2、2、3，和题目给出的示例完全匹配。

• 时间复杂度：所有操作均为哈希表常数级读写，最小值指针仅单调递增无回溯，均摊时间复杂度为O(1)
• 空间复杂度：和数组中不同数值的数量线性相关，远低于维护全量数组+堆的方案开销

内容的提问来源于stack exchange，提问作者himanshu kumar