题目描述
思路解析动画文字版
记牢一句:每回合削当前最高的两堆,让三堆拉平。也可以直接套公式 min(总和减最大堆, 总和//2)。下面逐回合演示。
总览 · 三堆石子摆好,每回合从两堆各取一颗记 1 分：上面三根柱子就是三堆石子:第一堆 6 颗,第二堆 7 颗,第三堆 8 颗,一共 21 颗。右边记分板显示当前得分 0,和场上还剩多少石子。接下来每回合都从当前最高的两堆各拿一颗、加一分,看着石子一点点被削平。
第 1 回合 · 先挑当前最高的两堆：第 1 回合。眼下三堆是 6、7、8。把它们从小到大看是 6 ≤ 7 ≤ 8,最高的两堆分别是 8 和 7(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
第 1 回合 · 两堆各取一颗,得分 1：从这两堆各拿走一颗:一堆从 8 减到 7,另一堆从 7 减到 6,得分加到 1。三堆现在是 6、6、7。还都能继续配对,进入下一回合。
第 2 回合 · 先挑当前最高的两堆：第 2 回合。眼下三堆是 6、6、7。把它们从小到大看是 6 ≤ 6 ≤ 7,最高的两堆分别是 7 和 6(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
第 2 回合 · 两堆各取一颗,得分 2：从这两堆各拿走一颗:一堆从 7 减到 6,另一堆从 6 减到 5,得分加到 2。三堆现在是 5、6、6。还都能继续配对,进入下一回合。
第 3 回合 · 先挑当前最高的两堆：第 3 回合。眼下三堆是 5、6、6。把它们从小到大看是 5 ≤ 6 ≤ 6,最高的两堆分别是 6 和 6(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
第 3 回合 · 两堆各取一颗,得分 3：从这两堆各拿走一颗:一堆从 6 减到 5,另一堆从 6 减到 5,得分加到 3。三堆现在是 5、5、5。还都能继续配对,进入下一回合。
第 4 回合 · 先挑当前最高的两堆：第 4 回合。眼下三堆是 5、5、5。把它们从小到大看是 5 ≤ 5 ≤ 5,最高的两堆分别是 5 和 5(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
第 4 回合 · 两堆各取一颗,得分 4：从这两堆各拿走一颗:一堆从 5 减到 4,另一堆从 5 减到 4,得分加到 4。三堆现在是 4、4、5。还都能继续配对,进入下一回合。
第 5 回合 · 先挑当前最高的两堆：第 5 回合。眼下三堆是 4、4、5。把它们从小到大看是 4 ≤ 4 ≤ 5,最高的两堆分别是 5 和 4(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
第 5 回合 · 两堆各取一颗,得分 5：从这两堆各拿走一颗:一堆从 5 减到 4,另一堆从 4 减到 3,得分加到 5。三堆现在是 3、4、4。还都能继续配对,进入下一回合。
第 6 回合 · 先挑当前最高的两堆：第 6 回合。眼下三堆是 3、4、4。把它们从小到大看是 3 ≤ 4 ≤ 4,最高的两堆分别是 4 和 4(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
第 6 回合 · 两堆各取一颗,得分 6：从这两堆各拿走一颗:一堆从 4 减到 3,另一堆从 4 减到 3,得分加到 6。三堆现在是 3、3、3。还都能继续配对,进入下一回合。
第 7 回合 · 先挑当前最高的两堆：第 7 回合。眼下三堆是 3、3、3。把它们从小到大看是 3 ≤ 3 ≤ 3,最高的两堆分别是 3 和 3(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
第 7 回合 · 两堆各取一颗,得分 7：从这两堆各拿走一颗:一堆从 3 减到 2,另一堆从 3 减到 2,得分加到 7。三堆现在是 2、2、3。还都能继续配对,进入下一回合。
第 8 回合 · 先挑当前最高的两堆：第 8 回合。眼下三堆是 2、2、3。把它们从小到大看是 2 ≤ 2 ≤ 3,最高的两堆分别是 3 和 2(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
第 8 回合 · 两堆各取一颗,得分 8：从这两堆各拿走一颗:一堆从 3 减到 2,另一堆从 2 减到 1,得分加到 8。三堆现在是 1、2、2。还都能继续配对,进入下一回合。
第 9 回合 · 先挑当前最高的两堆：第 9 回合。眼下三堆是 1、2、2。把它们从小到大看是 1 ≤ 2 ≤ 2,最高的两堆分别是 2 和 2(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
第 9 回合 · 两堆各取一颗,得分 9：从这两堆各拿走一颗:一堆从 2 减到 1,另一堆从 2 减到 1,得分加到 9。三堆现在是 1、1、1。还都能继续配对,进入下一回合。
第 10 回合 · 先挑当前最高的两堆：第 10 回合。眼下三堆是 1、1、1。把它们从小到大看是 1 ≤ 1 ≤ 1,最高的两堆分别是 1 和 1(标绿的这两根)。就从这两堆各取一颗,把它们压下去,别让最高的堆越拖越突出。
第 10 回合 · 两堆各取一颗,得分 10：从这两堆各拿走一颗:一堆从 1 减到 0,另一堆从 1 减到 0,得分加到 10。三堆现在是 0、0、1。有堆见底了,场上空堆变多,要留意还够不够两堆非空。
收尾 · 出现两个空堆,游戏停止：现在三堆是 0、0、1,其中两堆已经空了(标灰)。规则说有两个空堆就停,剩下标红那 1 颗石子孤零零一堆,一回合得动两堆,它再也找不到搭档,只能剩着。最终得分 10。用公式验一下:总和 21 减最大堆 8 得 13,总和的一半是 10,两者取小正好是 10,对上了。
边界:全 1 时得 1 分并剩一颗;最大堆过大时得分被「总和减最大堆」卡住;最大堆不过大时得分是「总和//2」。
面试重点:贪心削最高两堆同时顶住两个上限;可用公式 min(总和减最大堆, 总和//2) 一步算;这是「最大一项 vs 其余之和」的配对套路,和任务调度器同源。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def maximumScore(self, a: int, b: int, c: int) -> int: s = sorted([a, b, c]) ans = 0 while s[1]: ans += 1 s[1] -= 1 s[2] -= 1 s.sort() return ans复杂度
- 时间：O(a+b+c)，每回合总石子数减 2,所以回合数最多是总和的一半,也就是 O(a+b+c) 这个量级;每回合里排序的只有三个元素,是常数功夫。若改用等价公式 min(总和减最大堆, 总和//2) 直接算,则是 O(1)
- 空间：O(1)，按峰值算,自始至终只用一个长度为 3 的数组存三堆、外加得分和几个下标变量,占用是固定的常数,和石子多少无关,所以是 O(1)
易错点
面试追问把动画讲成自己的话
追问为什么每回合取当前最高的两堆一定是最优的?
追问不用一回合回合地模拟,能直接算出答案吗?
追问这题和「任务调度器」「重构字符串」这类题有什么共性?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最大平均通过率
LeetCode 1792 · 中等 · 沿着 堆套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题