659.md

659 Split Array into Consecutive Subsequences

Description

link

---

Solution

这题一开始我的思路是使用heap保存所有可能形成的list，但是后来发现并不需要，只需要保存他们的长度，在一个dict当中即可，使用最后一位数字作为key

记得删除lens当中已经为空的数组，否则在get的时候很可能得不到[0]

---

Code

Complexity T : O(n(log(n))

class Solution:
    def isPossible(self, nums: List[int]) -> bool:
        lens = collections.defaultdict(list)
        for n in nums:
            l = heapq.heappop(lens.get(n - 1, [0]))
            if not lens[n - 1]:
                del lens[n - 1]
            heapq.heappush(lens[n], l + 1)
        for k, v in lens.items():
            if v and min(v) < 3:
                return False
        return True