[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为的序列数。代码如下：

	class Solution {
	public:
	bool isPossible(vector<int>& nums) {
	int len = nums.size(), shortSeq = 0;
	unordered_map<int, priority_queue<int, vector<int>, greater<int>>> map;
	for(int i = 0; i < len; ++i)
	{
	int curr = nums[i];
	if(i > 0 && map.find(curr - 1) != map.end())
	{
	int currLen = map[curr - 1].top();
	map[curr - 1].pop();
	if(map[curr - 1].empty())
	map.erase(curr - 1);
	map[curr].push(currLen + 1);
	if(currLen == 2)--shortSeq;
	}
	else
	{
	map[curr].push(1);
	++shortSeq;
	}
	}
	return !shortSeq;
	}
	};

view raw Split Array into Consecutive Subsequences_3.cpp hosted with ❤ by GitHub

这道题还有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)，代码如下:

	class Solution {
	public:
	bool isPossible(vector<int>& nums) {
	int len = nums.size(), i = 0, prev = -1;
	//dp[i][1]/dp[i][2] represents number of consecutive subsequences with length 1/2 ending at i
	//dp[i][3] represents number of consecutive subsequences with length >= 3 ending at i
	vector<vector<int>> dp;
	while(i < len)
	{
	int num = nums[i], count = 0;
	while(i < len && nums[i] == num)
	{
	++i;
	++count;
	}
	if(dp.empty() || num != prev + 1)
	{
	if(dp.size() && (dp.back()[1] != 0 || dp.back()[2] != 0 || dp.back()[3] <= 0))
	return false;
	vector<int> seq(4, 0);
	seq[1] = count;
	seq[2] = 0;
	seq[3] = 0;
	dp.push_back(seq);
	}
	else
	{
	int p1 = dp.back()[1], p2 = dp.back()[2], p3 = dp.back()[3];
	//there is sequence with length 1/2 that we cannot fill
	if(count < p1 + p2)
	return false;
	vector<int> seq(4, 0);
	seq[2] = p1;
	seq[3] = min(count - p1, p2 + p3);
	seq[1] = max(0, count - (p1 + p2 + p3));
	dp.push_back(seq);
	}
	prev = num;
	}
	return dp.back()[1] == 0 && dp.back()[2] == 0 && dp.back()[3] > 0;
	}
	};

view raw Split Array into Consecutive Subsequences_1.cpp hosted with ❤ by GitHub

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

	class Solution {
	public:
	bool isPossible(vector<int>& nums) {
	if(nums.size() < 3)return false;
	int len = nums.size(), i = 0, prev = nums[0] - 2;
	//dp[i][1]/dp[i][2] represents number of consecutive subsequences with length 1/2 ending at i
	//dp[i][3] represents number of consecutive subsequences with length >= 3 ending at i
	vector<vector<int>> dp(2, vector<int>(3, 0));
	int e = 1;
	while(i < len)
	{
	int num = nums[i], count = 0;
	while(i < len && nums[i] == num)
	{
	++i;
	++count;
	}
	if(num != prev + 1)
	{
	if(dp[e ^ 1][1] != 0 || dp[e ^ 1][2] != 0)
	return false;
	dp[e][1] = count;
	dp[e][2] = 0;
	dp[e][3] = 0;
	}
	else
	{
	int p1 = dp[e ^ 1][1], p2 = dp[e ^ 1][2], p3 = dp[e ^ 1][3];
	//there is sequence with length 1 or 2 that we cannot fill
	if(count < p1 + p2)
	return false;
	dp[e][1] = max(0, count - p1 - p2 - p3);
	dp[e][2] = dp[e ^ 1][1];
	dp[e][3] = min(count - p1, p2 + p3);
	}
	prev = num;
	e ^= 1;
	}
	return dp[e ^ 1][1] == 0 && dp[e ^ 1][2] == 0 && dp[e ^ 1][3] > 0;
	}
	};

view raw Split Array into Consecutive Subsequences_2.cpp hosted with ❤ by GitHub