给定一个升序排列的数组num,将其拆分为1个或多个子序列,只有当每个子序列由连续的整数组成且长度至少为3时,才返回True。举例如下。
输入:[1,2,3,3,4,5]
输出:True
说明:你可以将它们分为两个长度为3且连续的子序列,分别为[1,2,3]和[3,4,5]。
思路:每次总是把顺子(连续增加的序列)中最短的那个序列找出来,然后把顺子的长度加1,压入优先队列。这里主要考查哈希表和优先队列的组合使用,有一定的难度。
首先对于元素1,因为优先队列里面没有元素,此时顺子的长度是1,把元素1以及其长度1压入队列。
对于第二个元素2,因为1已经在优先队列里面,出队列,同时增加顺子的长度为2,把元素2以及对应的长度2压入队列。
对于第三个元素3,因为2已经在优先队列里面,出队列,同时增加顺子的长度为3,把元素3以及对应的长度3压入队列。
对于第四个元素3,因为2不在优先队列里面,所以设置此时顺子的长度为1,把3以及顺子的长度1压入优先队列。
对于第五个元素4,因为3已经在优先队列里面,此时元素3的长度有两个,一个是3,另一个是1,我们需要把长度最小的那个元素从优先队列里面提取出来,同时把长度增到2,把元素4以及长度2压入优先队列。
第六个元素是5,因为4已经在优先队列里面,出队列,同时把其长度增加1,然后把元素5和其长度3压入优先队列。
最后检查每个元素是否在优先队列里面,而且其长度是否小于3。如果不是的话,那么就不能组成顺子。
代码清单5-5 判断数组是否可以拆分为连续的子序列