LeetCode 846中等贪心
一手顺子 图解题解
这道题到底在问什么
把手牌分成若干组，每组 groupSize 张连续牌，判断能否分完。
- 示例
- hand=[1,2,3,6,2,3,4,7,8], groupSize=3 → true
最优解：一步一步想明白
- 3随便从中间开组可能占掉小牌，导致前面无法成组。
- 4每次从当前最小还剩牌 x 开始，扣 x,x+1,... 这组连续牌。
- 5最小牌 1 开始先数清每张牌几张；之后每次都拿最小的牌开一组。
- 6扣掉 1,2,3最小牌没有退路，只能领一组；连号的 2、3 被一起带走。
- 7下一个最小是 2重复同一招：永远从剩下的最小牌开组。
- 8扣掉 2,3,4最后三张刚好成一组。
- 9最后 6,7,8 也成组每张牌都用光且都在连号组里 → 成功。
- 12一句话记住：每次从当前最小还剩牌 x 开始，扣 x,x+1,... 这组连续牌。
- 15雷区实演：随便从中间开组可能占掉小牌，导致前面无法成组。换个开组顺序就翻车：最小牌必须最先被消化。
- 22这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=greedy 连刷同类题；卡住时用 AI 答疑问“我的状态定义哪里不稳”。
⚠️ 容易写错的地方
✗ 错：忘了先判 len(hand) % groupSize
✓ 对：不能整除 → 直接 false
每组恰好 groupSize 张，总牌数不是它的整数倍就一定有剩牌，提前剪枝。
✗ 错：从任意牌 / 最大牌开始凑组
✓ 对：永远从「当前还剩的最小牌」开组
最小牌没有更小的牌能带它，只能自己当某组开头；不先消化它，它必落单。
✗ 错：连号中某张不够却继续往下扣
✓ 对：cnt[y] ＜ need 立即 false
要连 x..x+groupSize−1，中间任一数剩余不够当前需求，这组就连不出，整手失败。
完整代码（Python / C++ / Java）
Python
class Solution:
def isNStraightHand(self, hand, groupSize):
if len(hand) % groupSize:
return False
from collections import Counter
cnt = Counter(hand)
for x in sorted(cnt):
need = cnt[x]
if need > 0:
for y in range(x, x + groupSize):
if cnt[y] < need:
return False
cnt[y] -= need
return TrueC++
class Solution {
public:
bool isNStraightHand(vector<int>& hand, int groupSize) {
if (hand.size() % groupSize) return false;
map<int,int> cnt;
for (int x : hand) cnt[x]++;
for (auto& [x, need] : cnt) if (need > 0) {
for (int y=x; y<x+groupSize; y++) {
if (cnt[y] < need) return false;
cnt[y] -= need;
}
}
return true;
}
};Java
class Solution {
public boolean isNStraightHand(int[] hand, int groupSize) {
if (hand.length % groupSize != 0) return false;
TreeMap<Integer, Integer> cnt = new TreeMap<>();
for (int x : hand) cnt.put(x, cnt.getOrDefault(x, 0) + 1);
for (int x : new ArrayList<>(cnt.keySet())) {
int need = cnt.get(x);
if (need > 0) {
for (int y=x; y<x+groupSize; y++) {
if (cnt.getOrDefault(y, 0) < need) return false;
cnt.put(y, cnt.get(y) - need);
}
}
}
return true;
}
}套路模板 · 连号分组贪心骨架
# 连号分组 / 一手顺子 · 贪心骨架
if len(hand) % groupSize: return False # 不整除先剪枝
cnt = Counter(hand)
for x in sorted(cnt): # 从最小点数开始
need = cnt[x]
if need == 0: continue
for y in range(x, x + groupSize): # 连出一组 x..x+groupSize-1
if cnt[y] < need: return False # 某张不够 → 失败
cnt[y] -= need
return True复杂度
时间复杂度
O(n log n)
排序（或用有序结构取最小）主导；之后每张牌被消费一次
空间复杂度
O(n)
计数表 Counter 最多存 n 张牌的频次
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 一手顺子 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的贪心为什么是对的（正确性）？+
交换论证：当前最小牌 x 在任何合法方案里都只能当某组开头（没有更小的牌让它做中间/结尾），而它能连的组 x..x+groupSize−1 是唯一选择。所以「每次拿最小牌开一组」的每一步都是被迫且唯一的，不会错过任何可行解。
这道题为什么用「贪心」，换最直接的暴力解会差在哪？+
贪心抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。