友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
659. 分割数组为连续子序列
给你一个按 非递减顺序 排列的整数数组 nums 。
请你判断是否能在将 nums 分割成 一个或多个子序列 的同时满足下述 两个 条件：
-
每个子序列都是一个 连续递增序列（即，每个整数 恰好 比前一个整数大 1）。
-
所有子序列的长度 至少 为
3。
如果可以分割 nums 并满足上述条件，则返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,3,4,5] 输出：true 解释：nums 可以分割成以下子序列： [1,2,3,3,4,5] --> 1, 2, 3 [1,2,3,3,4,5] --> 3, 4, 5
示例 2：
输入：nums = [1,2,3,3,4,4,5,5] 输出：true 解释：nums 可以分割成以下子序列： [1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5 [1,2,3,3,4,4,5,5] --> 3, 4, 5
示例 3：
输入：nums = [1,2,3,4,4,5] 输出：false 解释：无法将 nums 分割成长度至少为 3 的连续递增子序列。
提示：
-
1 <= nums.length <= 104 -
-1000 <= nums[i] <= 1000 -
nums按非递减顺序排列
思路分析
哈希+最小堆。最初想法是先凑够三个序列，往上追加。提交测试发现有各种失败案例。
看题解，可以用哈希记录已有序列，最小堆筛选出相同结尾最小的序列的长度，优先在较短的队列上追加元素。这个思路和最初思路有很多相通之处。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-04-25 20:29:50
*/
public boolean isPossible(int[] nums) {
Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
for (int num : nums) {
if (!map.containsKey(num)) {
map.put(num, new PriorityQueue<>());
}
if (map.containsKey(num - 1)) {
Integer prevLength = map.get(num - 1).poll();
if (map.get(num - 1).isEmpty()) {
map.remove(num - 1);
}
map.get(num).offer(prevLength + 1);
} else {
map.get(num).offer(1);
}
}
for (Map.Entry<Integer, PriorityQueue<Integer>> entry : map.entrySet()) {
if (entry.getValue().peek() < 3) {
return false;
}
}
return true;
}