分割数组为连续子序列 图解题解

这道题到底在问什么

输入

nums=[1,2,3,3,4,5]

输出

true （拆成 [1,2,3] 和 [3,4,5]）

输入

nums=[1,2,3,4,4,5]

输出

false （剩下的凑不出长度 ≥ 3 的连续段）

最优解：一步一步想明白

1. 3核心口诀：能接尾就接尾，不能接就起一条新三连，都不行就 false。为什么优先接尾？因为接尾不浪费、还能让已有短序列变长，更容易达标。下面每一帧都在套这套规则。
2. 4第一步：数一遍每个数有几个，填进 cnt（剩余可用次数）。need 现在全是 0，因为还没有任何子序列在等着被接。
3. 5先把 need 读懂：need[x] 大于 0，就表示前面有现成的子序列结尾在 x-1，正张着嘴等一个 x。接下来从第 0 个开始扫。
4. 6扫到第 0 个 1。它还有剩（cnt[1]=1）。先查 need[1]=0：有没有序列正等着接 1？
5. 7没人等 1，那就用 1、2、3 现起一条长度 3 的新序列（绿色）。把 2、3 各扣 1 表示被领走，这条新序列结尾是 3，改成等 4：need[4] 加 1。
6. 8扫到第 1 个 2，但 cnt[2] 已经是 0，说明这个 2 早就被前面某条序列取走了，跳过它。
7. 92 没库存了，跳过。两张表都不动，继续看下一个。
8. 10扫到第 2 个 3。它还有剩（cnt[3]=1）。先查 need[3]=0：有没有序列正等着接 3？
9. 11没人等 3，那就用 3、4、5 现起一条长度 3 的新序列（绿色）。把 4、5 各扣 1 表示被领走，这条新序列结尾是 5，改成等 6：need[6] 加 1。
10. 12扫到第 3 个 3，但 cnt[3] 已经是 0，说明这个 3 早就被前面某条序列取走了，跳过它。
11. 133 没库存了，跳过。两张表都不动，继续看下一个。
12. 14扫到第 4 个 4。它还有剩（cnt[4]=1）。先查 need[4]=1：有没有序列正等着接 4？
13. 15有序列在等 4！把 4 接上去（绿色）。这条序列结尾从 3 变成 4，于是它改成等 5：need[4] 减 1、need[5] 加 1。优先接尾，不浪费。
14. 16扫到第 5 个 4，但 cnt[4] 已经是 0，说明这个 4 早就被前面某条序列取走了，跳过它。
15. 174 没库存了，跳过。两张表都不动，继续看下一个。
16. 18扫到第 6 个 5。它还有剩（cnt[5]=1）。先查 need[5]=1：有没有序列正等着接 5？
17. 19有序列在等 5！把 5 接上去（绿色）。这条序列结尾从 4 变成 5，于是它改成等 6：need[5] 减 1、need[6] 加 1。优先接尾，不浪费。
18. 20扫到第 7 个 5，但 cnt[5] 已经是 0，说明这个 5 早就被前面某条序列取走了，跳过它。
19. 215 没库存了，跳过。两张表都不动，继续看下一个。
20. 22扫完回放一下分配结果。绿色这 5 个是第一条 [1,2,3,4,5]，剩下灰色的 3、4、5 正好是第二条 [3,4,5]，两条都长度 ≥ 3。
21. 23全部扫完，一路都没卡住。8 个数正好拆成两条：[1,2,3,4,5] 和 [3,4,5]，两条都达标，返回 true。need 里残留的几个 6 只是「曾经等过」的记号，没有未完成的短序列。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        d = defaultdict(list)
        for v in nums:
            if h := d[v - 1]:
                heappush(d[v], heappop(h) + 1)
            else:
                heappush(d[v], 1)
        return all(not v or v and v[0] > 2 for v in d.values())

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, priority_queue<int, vector<int>, greater<int>>> d;
        for (int v : nums) {
            if (d.count(v - 1)) {
                auto& q = d[v - 1];
                d[v].push(q.top() + 1);
                q.pop();
                if (q.empty()) {
                    d.erase(v - 1);
                }
            } else {
                d[v].push(1);
            }
        }
        for (auto& [_, v] : d) {
            if (v.top() < 3) {
                return false;
            }
        }
        return true;
    }
};

import java.util.*;
class Solution {
    public boolean isPossible(int[] nums) {
        Map<Integer, PriorityQueue<Integer>> d = new HashMap<>();
        for (int v : nums) {
            if (d.containsKey(v - 1)) {
                PriorityQueue<Integer> q = d.get(v - 1);
                d.computeIfAbsent(v, k -> new PriorityQueue<>()).offer(q.poll() + 1);
                if (q.isEmpty()) {
                    d.remove(v - 1);
                }
            } else {
                d.computeIfAbsent(v, k -> new PriorityQueue<>()).offer(1);
            }
        }
        for (PriorityQueue<Integer> v : d.values()) {
            if (v.peek() < 3) {
                return false;
            }
        }
        return true;
    }
}

复杂度

面试官可能追问