[LeetCode]Split Array into Consecutive Subsequences

我们可以用map来记录所有以k结尾的sequence的数量和长度，当我们到达nums[i]的时候：

• map存在以nums[i] - 1结尾的，代表我们可以填充之前的一个序列，我们将之前以nums[i] - 1结尾的序列删去，插入新的序列(显然如果可以填充进一个之前的序列的话，我们完全没有必要新开一个序列)
• map不存在以nums[i] - 1结尾的，代表我们必须新开始一个序列。

对于第二种情况我们很好理解，但是对于第一种情况，我们可能存在有多个以nums[i] - 1结尾的序列，我们选哪个去填充呢？我们这里采取greedy的思路，就是去填充最短的，首先如果存在a个以nums[i] - 1的序列，假设都是长度>=3的，那么填哪个都无所谓。如果其中有b个长度<=3的话，假设将其补齐成长度等于3的序列需要k个数，那么每次填最短的可以保证我们用k个数可以将其补齐成长度为3的序列， 如果做不到，return false。显然在这greedy的做法可以让我们达到最优解，所以是可行的。

那么我们如何找到最短的呢，这里我们用priority_queue来帮助我们达到这一目的，如果最后我们发现还有长度<3的序列说明我们无法split，否则说明可以，时间复杂度O(n * log n)，因为我们每次要用优先队列找最短的，空间复杂度O(k)，k为可以split为的序列数。代码如下：

这道题还有O(n)的做法，我们统计出每个数有多少个，然后用DP数组记录这几个值：

1. DP[i][1]代表以i结尾，长度为1的sequence的数量
2. DP[i][2]代表以i结尾，长度为2的sequence的数量
3. DP[i][3]代表以i结尾，长度>=3的sequence的数量

假设i有count个，递推方程如下：

1. DP[i][1] = max(0, count - (DP[i][1] + DP[i][2] + DP[i][3]))
2. DP[i][2] = DP[i - 1][1]
3. DP[i][3] = min(count - DP[i - 1][1], DP[i][2] + DP[i][3])

首先count一定要满足count >= DP[i - 1][1] + DP[i - 1][2]，否则以i - 1结尾的长度小于3的序列会有填不满的，这样的话我们return false。在count满足上述条件下，以i结尾的长度为2的序列可以完全又以i - 1结尾的序列转化而来，所以DP[i][2] = DP[i - 1][1]。当i填补完i - 1结尾长度为1的序列后，可以继续填补i - 1结尾长度>=2的序列，存在两种情况：

• 剩下的i可以填补所有i - 1结尾长>=2的序列，还有的多，DP[i][2] + DP[i][3]
• 剩下的i不够填补所有i - 1结尾长>=2的序列，count - DP[i - 1][1]

对于i结尾长度为1的序列，同理存在两种情况：

• i在填补完所有以i - 1结尾的序列之后，还有的多，增加count - (DP[i][1] + DP[i][2] + DP[i][3])个以i结尾长度为1的序列
• 否则，为0个

根据上面的递推方程我们可以写出解法，时间复杂度O(n)，空间复杂度O(n)，代码如下:

空间我们可以进一步优化为常数空间，代码如下：