🎮 贪心策略的两种命运：可重复选vs不可重复选

能摆的时候别卷，该卷的时候别摆

村长又来信了。这次竟然是让村里的老黄牛慢悠悠驮过来的——我怀疑村长把信鸽的口粮预算都给砍了，这老头在省钱的路上已经走火入魔。我展开纸条一看：“ 小白，勇士团下周开荒新副本，出发前要做战力波动评估！规则如下：给一个数组 nums 和一个整数 k，从中选恰好 k 个非空子数组。子数组可以重叠，同一个子数组可以被选择超过一次。每个子数组的值 = 最大值 - 最小值，求最大可能的总值。”

我盯着“可以重叠”和“可以被选择超过一次”这两行字，手里的拨火棍差点掉进锅炉里。这不就是明摆着让我薅羊毛吗？整个数组就是天然的极差冠军——既然同一段能刷 k 遍，那就把极差冠军往死里薅——就像在游戏里找到经验值最高的怪，然后挂机刷 k 次，连走位都省了。

return (max(nums) - min(nums)) * k

一行流，三十秒 AC，我甚至有空给自己泡了杯茶。茶杯端到嘴边，我忽然顿住了——不对劲。非常不对劲。

我见过太多副本了——加一个约束，难度翻倍；砍一个约束，难度减半。但这题居然专门强调“子数组可以重叠”“同一个子数组可以反复选”——也就是说，“子数组之间不能重叠”和“每个子数组只能选一次”这两个最要命的约束全被砍了，直接退化成一个极值问题，难度标签形同虚设。这不是放水，这是泄洪啊。

事出反常必有妖。我正盯着屏幕发呆，后脑勺"啪"地挨了一下。不重不轻，力道精准得像调试过阈值的触发器。果然又是老勇者，手指还保持着弹脑瓜崩的姿势，“AC 了还发呆？不像你啊——”

“喂，大师，下次咱换个出场方式行吗？” 我揉着后脑勺嘟囔道，“这道题简单到诡异啊。” 我把题目指给他看，“‘可以重叠’、‘可以反复选’——约束全砍了，一行代码就搞定，策划是不是被盗号了？”

老勇者笑了：“策划没被盗号，他这是在告诉你——贪心的极致就是摆烂。既然能无限次选择最优解，就别整那些花里胡哨的，直接把最优解复制 k 份。你想想，如果连摆烂的机会都不给你，直接上硬核约束，你连这个一行流的心得都悟不到，直接被困难版锤进地里。”

“……所以，策划用心良苦就是为了教我读题？”

”能看穿什么时候该摆烂，也是一种本事。不过——"

老勇者话锋一转，眼神突然变得危险起来，“如果加上约束，阁下又将如何应对？”

他伸手拿起那张皱巴巴的羊皮纸，掏出随身携带的红笔——那个瞬间我甚至怀疑他是不是专门等着改我的题目——在纸上画了画，然后又递回给我。我低头一看：

“选择恰好 k 个不同的非空子数组。子数组可以重叠，同一个子数组不可以被选择超过一次。”

我倒吸一口凉气，手里的茶杯差点跟着羊皮纸一块儿掉进锅炉里。“不同的”非空子数组，“同一个子数组不能被选择超过一次”——约束一加，难度飞天。刚才一行流抓最肥的羊反复薅，现在每只羊只让薅一次，这不得挑出前k个最肥的羊？

我开始盘算：直接上暴力把所有可能的子数组全列出来，算极差，排序，取前 k 大。但长度为 n 的数组，子数组数量 n(n+1)/2，O(n²) 的候选集，n 大了直接炸，评测机怕是要给我唱一首《超时咏》。

“等等——题目只改了‘不能重复选同一段’，没禁止段之间重叠！！” 我拿着笔在纸上戳了戳，“既然可以重叠，那我不需要担心选了一段之后堵死其他段的问题。整个数组的极差max - min是冠军，只能用一次。把它用掉之后，第二大极差要么是抠掉最大值后剩下的区间，要么是抠掉最小值后剩下的区间——把最值抠掉，极差才可能变小。然后，季军就是从亚军的残骸里继续抠最值——”

我一拍脑门，“这不就是一个贪心扩展的过程吗？搞个大根堆维护候选池，每次挑极差最大的区间用掉，然后把它‘切开’——抠掉最大值或最小值之后，剩下的子区间重新扔回候选池里。重复 k 次，累加极差，搞定。大根堆！这可是高级数据结构，这把稳了。”

“方向是对的。”老勇者点点头，然后毫不留情地浇了一盆冷水，“但你的刀法有问题——候选池里的区间数量会指数爆炸，你这不叫堆，叫炸弹。想象一下，每次切一下产生两个新区间，k 次就是 2^k 个候选，你的堆会变成二叉树的坟场。"

我刚刚燃烧起来的小宇宙瞬间被浇灭，整个人像被触发了 NullPointerException 一样瘫在椅子上。大根堆都救不了我，那还有什么能救？

老勇者撇了我一眼，拿起笔在草稿纸上画了一条长线，标上刻度 0 到 n。“换个角度。别再跟切分死磕了。任意一个子数组都由两个东西决定——左端点 l 和右端点 r。固定 l，极差随 r 怎么变？”

我想了想：“r 越往右，区间越长，最大值只会变大或不变，最小值只会变小或不变——所以极差只增不减？”

“对。“老勇者在纸上画了几条平行的隧道，每条从不同起点出发，箭头齐刷刷指向右边，“”这就像玩一个挖矿游戏——固定起点，隧道越长，挖到的宝藏价值差越大。“

”初始地图上有 n 个起点，你站在每个起点 i，把每条隧道都从起点一路挖到最深处 [i, n)，把这 n 个候选段全扔进一个最大堆里。弹出堆顶——当前极差最大的区间——累加价值差进答案，然后把当前隧道在深度上缩一格，也就是把右端点从 r 减到 r-1，再压回堆里作为新的候选。如此重复 k 次即可。"

我盯着那排箭头：“等等——所以不是切碎区间？而是固定左端点，只缩短右端点？让堆里永远只有 n 个候选？！”

“对。每次弹出 [l, r)，压回 [l, r-1)。候选数恒定 n 个，不会指数爆炸。而且对于固定 l，极差随 r 单调不减，每次取堆顶一定是全局最优，贪心正确性有保证——这就是’隧道模型’，只在一个方向缩，不往两个方向切。"

“但每次缩一格要重新扫一遍极差不还是 O(n)，这是把爆炸从堆里挪到了查询里吗？“我皱着眉头，感觉这个方案还是有致命伤。

老勇者嘴角勾起一抹神秘的微笑：“所以你需要一件神器——能让任意区间的极差查询在 O(1) 时间内完成的神器。”

“O(1)？！“我差点从椅子上跳起来，“难道不用遍历就能知道最大值和最小值？这违反了信息论吧？在每个位置都装个预知未来的水晶球？”

“差不多。“老勇者真的从怀里掏出了一块……石板？上面刻满了密密麻麻的符文，“这叫稀疏表（Sparse Table），上古时代用来快速查询区间最值的魔法阵。核心思想很简单——提前把所有可能用到的区间的最值都算好存起来，用的时候直接查表。”

他抬手在空中划出一串发光的代码，稀疏表像闪亮的星星一样悬在半空：

def op(a, b):
    return (min(a[0], b[0]), max(a[1], b[1]))

class ST:
    def __init__(self, a):
        n = len(a)
        w = n.bit_length()
        st = [[None] * n for _ in range(w)]
        st[0] = [(x, x) for x in a]
        for i in range(1, w):
            for j in range(n - (1 << i) + 1):
                st[i][j] = op(st[i-1][j], st[i-1][j + (1 << (i-1))])
        self.st = st
    
    # 查询 [l, r) 左闭右开，返回极差
    def query(self, l, r):
        k = (r - l).bit_length() - 1
        mn, mx = op(self.st[k][l], self.st[k][r - (1 << k)])
        return mx - mn

“等等等等，“我被那一堆位运算晃得眼晕，“这玩意儿怎么看都像黑魔法……1 « i 是什么鬼？”

老勇者叹了口气，拿起笔在石板上画了个示意图：“别被位运算吓到。我给你翻译成人话——”

“第一层魔法：预处理所有 2 的幂次长度的区间。你看 st[0] 存的是长度为 1 的区间（就是单个元素），st[1] 存的是长度为 2 的区间，st[2] 存的是长度为 4 的区间，以此类推。1 « i 就是 2^i，左移一位相当于乘以 2。”

他在纸上画了一排格子：

原始数组: [1, 3, 2, 5, 4]

st 0 : [(1,1), (3,3), (2,2), (5,5), (4,4)] st1: [(1,3), (2,3), (2,5), (4,5)] st2: [(1,5), (2,5)]

" st[ i ] [ j ] 表示从位置 j 开始、长度为 2^i 的区间的 (最小值, 最大值)。关键在于——长区间可以由两个短区间拼出来。比如，长度为 4 的区间 [j, j+4) 可以拆成两个长度为 2 的区间 [j, j+2) 和 [j+2, j+4)，取它们的 min 和 max 就行。这就是 op 函数的作用——合并两个区间的极值。”

我盯着那个递推式 st[ i ] [ j ] = op(st[ i-1 ] [ j ] , st[ i-1 ] [ j + (1 « (i-1)) ])：“所以这是先把短的算好了，长的直接拼？”

“没错。ST 表预处理的复杂度是 O(n log n)，因为最多有 log n 层，每层最多 n 个元素。” 老勇者指着 query 方法，“真正的魔法在这里——怎么在 O(1) 时间内查询任意长度的区间？”

“假设我要查 [l, r)，长度是 len = r - l。我们需要找到不超过 len 的最大的 2 的幂次。比如 len=5，最大的幂次是 4（也就是 2^2），然后用两个长度为 4 的区间覆盖 [l, r)——一个从左边开始 [l, l+4)，一个从右边结束 [r-4, r)。这两个区间一定有重叠，但没关系，我们要的是最大值和最小值，重叠部分不影响结果。”

他在纸上画了个覆盖示意图：

数组: [1, 3, 2, 5, 4, 6, 3] |————| ← [l, l+4) 长度4 |————| ← [r-4, r) 长度4 |—————| ← [l, r) 长度5

“k = (r - l).bit_length() - 1 就是在找这个最大的幂次。op(self.st[ k ] [ l ], self.st[ k ] [ r - (1 « k) ]) 就是把两个区间拼起来，返回 (最小值, 最大值)，相减就是极差。”

我感觉脑子里有什么东西突然连通了：“所以稀疏表就是提前背好了所有标准长度（1, 2, 4, 8, 16…）的区间攻略，遇到任何长度的查询，就用两个标准区间拼出来？这确实是 O(1)，因为只需要查两次表再加一次合并！”

“对。不过要注意，稀疏表只能处理静态数组的区间查询，不能修改元素。如果要支持修改，就得用线段树或者树状数组。但这道题不需要修改，所以稀疏表是最优解。”

老勇者接着写下了主逻辑：初始化堆的时候，把每个起点 i 对应的最长隧道 [i, n) 的极差塞进去。因为隧道长度的缩减只会导致极差变小或不变，初始堆已经满足大根堆性质，连 heapify 都省了。循环 k 次，每次弹出堆顶，累加极差，然后把同一隧道缩一格 [l, r-1) 压回去。如果堆顶的极差已经等于 0，说明剩下的都是极差为 0 的区间，可以直接收工。

def maxTotalValue(self, nums, k):
    n = len(nums)
    st = ST(nums)
    # 最大堆: (极差, l, r)，初始每条隧道挖到最深处
    h = [(st.query(i, n), i, n) for i in range(n)]
    
    ans = 0
    for _ in range(k):
        d, l, r = h[0]
        if d == 0:  # 极差为 0，收工
            break
        ans += d
        # 弹出堆顶，同一隧道缩一格再压回去
        heapreplace_max(h, (st.query(l, r-1), l, r-1))
    return ans

我盯着这段代码，感觉像在看一个动态的挖矿图。堆里始终只有 n 个候选——每条矿脉一个。每次取走堆顶收益最大的矿段，同一条矿脉往浅层退一格，重新排队。稀疏表像一台地质探测仪，O(1) 就能查任意矿段的价值差。ST 表预处理O(n log n)，查询区间最值 O(1)。堆操作一次 O(log n)，k 次 O(k log n)。总复杂度 O(n log n + k log n)，稳稳扛住十万级。

“隧道模型 + 贪心堆 + 稀疏表，“我靠在椅背上，把这三个词在嘴里嚼了一遍，“固定一端，单调扩展，堆维护全局最优。极差查询交给 ST 表。这比我那套切分方案强太多了——那是中间开花，指数爆炸；这是单端收缩，候选数恒定。同一个贪心思路，区别这么大。”

老勇者拍了拍我的肩膀，转身向门口走去：“固定一端、贪心另一端，这种’隧道模型’在很多区间选 k 大的题里都能用。算法优化往往就是换个角度看问题，消除不必要的计算。记住，当你发现候选集要爆炸的时候，问问自己：能不能固定一个维度，只让另一个维度动？”

走到门口，他顿了顿，回头补了一句，眼神里闪烁着某种兴奋的光芒：“下次要是再加个约束——‘子数组不能重叠’的变种题，记得叫我——那时候，才是真正的战斗开始。动态规划的地狱之门，会为你敞开。”

我打了个寒颤，默默保存了今天的代码，顺手给文件加了个备份——万一哪天真的要用到呢？毕竟，在这个充满约束的世界里，唯一不变的就是变化本身。

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。