Question

659. 分割数组为连续子序列

English Version

题目描述

给你一个按 非递减顺序 排列的整数数组 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 按非递减顺序排列

解法

方法一：哈希表 + 优先队列（小根堆）

由于题目中的子序列是由连续整数组成的，因此，只要知道子序列的最后一个数以及子序列的长度，就能够确定子序列。

我们可以使用哈希表存储每个子序列的最后一个数，使用优先队列存储当前数作为子序列的末尾时，子序列的长度。我们要优先选择长度较短的子序列，因此使用小根堆。

遍历数组 nums，对于当前遍历到的数 num，如果 num 不能加入到任何子序列中，那么我们就创建一个新的子序列，长度为 1；否则，我们就将 num 加入到某个子序列中，具体的子序列是哪个呢？我们可以从 num - 1 对应的子序列中取出一个长度最短的子序列，将 num 加入到该子序列中，然后将该子序列的最后一个数更新为 num，同时将该子序列的长度加 1。

如果我们遍历完数组 nums，优先队列中所有的子序列的长度都不小于 3，那么我们就可以将数组 nums 分割成若干个子序列，否则，我们就无法将数组 nums 分割成若干个子序列。

时间复杂度 $O(n\log n)$，其中 $n$ 是数组 nums 的长度。空间复杂度 $O(n)$。

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())

class Solution {
  public boolean isPossible(int[] nums) {
    Map<Integer, PriorityQueue<Integer>> d = new HashMap<>();
    for (int v : nums) {
      if (d.containsKey(v - 1)) {
        var 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 (var v : d.values()) {
      if (v.peek() < 3) {
        return false;
      }
    }
    return true;
  }
}

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;
  }
};

func isPossible(nums []int) bool {
  d := map[int]*hp{}
  for _, v := range nums {
    if d[v] == nil {
      d[v] = new(hp)
    }
    if h := d[v-1]; h != nil {
      heap.Push(d[v], heap.Pop(h).(int)+1)
      if h.Len() == 0 {
        delete(d, v-1)
      }
    } else {
      heap.Push(d[v], 1)
    }
  }
  for _, q := range d {
    if q.IntSlice[0] < 3 {
      return false
    }
  }
  return true
}

type hp struct{ sort.IntSlice }

func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
  a := h.IntSlice
  v := a[len(a)-1]
  h.IntSlice = a[:len(a)-1]
  return v
}