動機

跟patch array一樣很有魔法的題目

Problem

You are given an integer array nums that is sorted in non-decreasing order.

Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:

  • Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).
  • All subsequences have a length of 3 or more.

Return true if you can split nums according to the above conditions, or false otherwise.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5] is a subsequence of [1,2,3,4,5] while [1,3,2] is not).

 

Example 1:

Input: nums = [1,2,3,3,4,5]Output: trueExplanation: nums can be split into the following subsequences:[1,2,3,3,4,5] --> 1, 2, 3[1,2,3,3,4,5] --> 3, 4, 5

Example 2:

Input: nums = [1,2,3,3,4,4,5,5]Output: trueExplanation: nums can be split into the following subsequences:[1,2,3,3,4,4,5,5] --> 1, 2, 3, 4, 5[1,2,3,3,4,4,5,5] --> 3, 4, 5

Example 3:

Input: nums = [1,2,3,4,4,5]Output: falseExplanation: It is impossible to split nums into consecutive increasing subsequences of length 3 or more.

 

Constraints:

  • 1 <= nums.length <= 104
  • -1000 <= nums[i] <= 1000
  • nums is sorted in non-decreasing order.

Sol

追蹤以此點為結尾的list長度，那list有兩種產生方式

  1. 加到尾巴: ... n-1 + n
  2. 當成新的list: n + n+1 + n+2
class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        left = Counter(nums)
        end = defaultdict(int)
        
        for n in nums:
            if left[n]:
                left[n] -= 1
                if end[n-1]:
                    end[n-1] -= 1
                    end[n] += 1
                elif left[n+1] and left[n+2]:
                    left[n+2] -= 1
                    left[n+1] -= 1
                    end[n+2] += 1
                else:
                    return False
        return True