一手顺子如何用贪心判断能否分组？（LeetCode 846）

简化版

每次从当前最小的牌开始，必须凑出一组连续长度为 groupSize 的顺子。

用有序计数表统计牌面；如果最小牌是 x 且还有 cnt 张，就必须从 x, x+1, ..., x+groupSize-1 各扣掉 cnt 张，缺任意一张都返回 false。

详细版

这题的贪心点在于「最小牌没有退路」。当前剩下的最小牌 x 不可能放到以更小数字开头的顺子里，因为那些牌已经不存在；它也不能跳过 x+1 去和更大的牌组成合法顺子。因此它只能作为某些顺子的起点。

实现时先判断总牌数是否能被 groupSize 整除。然后用 TreeMap<Integer, Integer> 记录每个牌面的数量，每轮取最小 key。如果最小 key 有 need 张，就从连续的 groupSize 个牌面中各扣 need 张，扣到 0 就删除。

boolean isNStraightHand(int[] hand, int groupSize) {
    if (hand.length % groupSize != 0) return false;
    TreeMap<Integer, Integer> map = new TreeMap<>();
    for (int x : hand) map.put(x, map.getOrDefault(x, 0) + 1);

    while (!map.isEmpty()) {
        int start = map.firstKey();
        int need = map.get(start);
        for (int x = start; x < start + groupSize; x++) {
            int c = map.getOrDefault(x, 0);
            if (c < need) return false;
            if (c == need) map.remove(x);
            else map.put(x, c - need);
        }
    }
    return true;
}

完整版教学

一、为什么最小牌必须作为起点

假设当前剩下的最小牌是 3。它如果不作为某组顺子的起点，就必须出现在 1,2,3 或 2,3,4 这类顺子里。但比 3 小的牌已经没有了，所以这些方案不可能成立。于是 3 唯一的合法位置就是某个顺子的第一张。

这就是本题贪心正确性的根。我们不是随便选一个局部方案，而是发现最小元素被约束到只有一种角色。只要当前最小牌无法向右凑出完整连续段，任何全局方案都不可能存在。

二、为什么一次要扣 need 张

如果最小牌 x 有 need 张，那么每一张 x 都必须开启一组顺子。也就是说需要 need 份 x+1、need 份 x+2，一直到 x+groupSize-1。只扣一张再循环当然也能做，但会重复扫描，效率更差。

例如 hand = [1,1,2,2,3,3]，groupSize=3。最小牌 1 有 2 张，所以必须同时扣掉两组：

需要 2 份: 1,2,3
扣完后: 1:0, 2:0, 3:0

如果 2 或 3 少于 2 张，就一定无法分成两组顺子。

三、有序映射的作用

贪心每轮都需要找到当前剩余最小牌，所以需要有序结构。Java 可以用 TreeMap，Python 可以先排序数组再配合计数表，C++ 可以用 map。关键不是具体容器，而是每轮处理时必须从最小剩余牌开始。

实现方式	找最小牌	适用场景
`TreeMap` / `map`	自动有序	代码直观，删除方便
排序数组 + HashMap	按排序顺序遍历	常见 LeetCode 写法
小根堆	可以找最小	删除和同步计数略繁琐

面试时用 TreeMap 最容易把贪心意图讲清楚。

四、流程图看清扣减过程

以 hand=[1,2,3,6,2,3,4,7,8]，groupSize=3 为例：

计数: 1:1 2:2 3:2 4:1 6:1 7:1 8:1
最小 1，需要 1 组: 扣 1,2,3
剩余: 2:1 3:1 4:1 6:1 7:1 8:1
最小 2，需要 1 组: 扣 2,3,4
剩余: 6:1 7:1 8:1
最小 6，需要 1 组: 扣 6,7,8
剩余为空，成功

这个过程每一步都消灭当前最小牌，因此不会留下无法处理的低牌。

五、复杂度与边界

如果使用 TreeMap，设不同牌面数量为 m，每次访问和更新有 O(log m) 成本，总体接近 O(n log m)。如果先排序，排序成本是 O(n log n)，之后每张牌被扣减有限次，整体也是常见可接受复杂度。

边界上，hand.length % groupSize != 0 可以提前失败。groupSize=1 时任何牌都能单独成组，答案为 true。牌面可能不连续、可能有大量重复，算法都通过计数表自然处理。

六、和区间覆盖类贪心的区别

这题不是选择「结束最早」或「覆盖最远」，而是选择「最小剩余元素的唯一归宿」。它和分发饼干、跳跃游戏的贪心证明不同，属于构造型贪心：先找出一个元素在任何合法解中必须怎么放，再把这个必须动作执行掉。

记忆钩子：顺子分组看最小牌，最小牌不能往左补，只能往右开组；开几组由它的张数决定。

七、常见误区与追问

误区：随便从某张牌开始凑顺子。 如果不优先处理最小牌，可能把小牌需要的后继牌提前用掉。
误区：最小牌有多张时只扣一张。 逻辑上可以但效率差，也更容易写出重复处理 bug。
误区：只检查是否存在连续牌面。 还要检查每个牌面的数量是否够用。
追问：为什么最小牌不能放在中间？ 因为中间位置需要更小的前驱牌，而当前它已经是最小剩余牌。
追问：复杂度是多少？ TreeMap 写法约 O(n log m)，排序写法约 O(n log n)。
追问：如果牌面范围很小能优化吗？ 可以用数组计数并从小到大扫描，省掉平衡树开销。

八、加强记忆

一手顺子的贪心锚点是「最小牌没有选择」。每次拿当前最小牌 x，它只能作为顺子起点；如果它有 need 张，就必须从 x 到 x+groupSize-1 每个数都扣 need 张。这个动作不是试探，而是任何合法解都必须包含的动作。记住「最小牌开组，数量决定组数，连续扣完再看下一个最小牌」，这题就不会写成回溯或乱序模拟。

简化版

详细版