###### tags: `Leetcode` `medium` `greedy` `heap` `hash` `python`

# 659. Split Array into Consecutive Subsequences

## [題目連結:] https://leetcode.com/problems/split-array-into-consecutive-subsequences/

## 題目:
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: true
Explanation: 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: true
Explanation: 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: false
Explanation: It is impossible to split nums into consecutive increasing subsequences of length 3 or more.

## 解題想法:
* 題目要求:給一非遞減的數組nums
* 求是否能切割成若干個subsequences
* 要求連續遞增(前後數均相差1)
* 長度至少大於3
* 想法: **greedy**+**hash_table+priority queue(heap)**
* 維護一個hash table: **defaultdict(list)**
* key:3
* 以3為結尾
* val:[1,3]
* 以3為結尾，目前可構成的長度組合有2條
* 1: 表示長度1，only3
* 3: 表示長度3，3,4,5串
* **hash_table的val，皆以heapq進行把關**
* Greedy想法:優先將當前的數放到長度最短的list中
* 判斷當前val的前一數，(val-1)為結尾的list是否存在
* 若存在，則heappop出以val-1為結尾的list中**最短的長度_newLen**
* 若不存在，將newLen=0
* 將新長度newLen+1使用heappush放入以val為結尾的List中

## Python:

from heapq import heappush,heappop
from collections import defaultdict
class Solution(object):
    def isPossible(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        dic=defaultdict(list) #key:以x為結尾，val:list[以x為結尾可構成的長度]
        for val in nums:
            getLen=dic[val-1]
            if not getLen:
                newLen=0
            else:
                newLen=heappop(getLen) #pop以val-1為結尾的最短長度
            #將可構成的新長度append加入以val為結尾的list
            heappush(dic[val],newLen+1)
        for key in dic:
            for val in dic[key]:
                if val<3:
                    return False
        return True
result=Solution()
ans=result.isPossible(nums = [1,2,3,3,4,5])
print(ans)