个人练习-Leetcode-659. Split Array into Consecutive Subsequences

题目链接：https://leetcode.cn/problems/split-array-into-consecutive-subsequences/

题目大意：给出一个非递减数列nums[]，判断其是否能被分割成若干个满足以下条件的子列：

• 长度大于等于3
• 元素严格递增且只相差1

子列的含义是：不改变元素的相对顺序，从原数列中抽取若干个元素组成新的数列。
分割的含义是：所有元素都会被分到某个子列，没有剩余。

思路：一开始的思路是，根据元素出现的次数，将其排列成若干个数列，比如在vector<vector<int>> subs中，subs[0]是仅出现一次的元素的数列；subs[1]是仅出现两次的元素的数列，以此类推。这样subs[][]就是一种对原数组的分割了，且保证了每个元素只出现一次。随后再对每个子列做调整，使其满足题意的两个条件。

长度大于等于3倒是不难解决，但要保证每个子列元素严格递增且增量为1并不容易。很难确定要从哪个子列中的哪个位置抽出哪个元素，放到另一个子列的哪个位置。似乎无法证明其可行性。

于是看了题解，原来用贪心做。不记录子列本身而是记录以x结尾的子列个数。

不过刚知道用贪心时我没有这么做，因为我的想法是：如果遍历到某个元素x，那么以x-1为结尾的子列应该是很多的，要挑选长度最短的那个子列才是最优的。于是在代码里多加了一层【以x-1为结尾的子列】的遍历（实际上这就是在记录子列本身了）。逻辑上应该没问题，然而时间超了…

这一版代码如下：

class Solution {
public:bool isPossible(vector<int>& nums) {map<int, vector<vector<int>>> endwithx;for (auto num : nums) {if (endwithx.find(num-1) == endwithx.end() || endwithx[num-1].size() == 0) {vector<int> tmp(1, num);endwithx[num].push_back(tmp);}else {vector<int> tgt;int min_len = endwithx[num-1][0].size(), min_idx = 0;for (int i = 1; i < endwithx[num-1].size(); i++) {auto sa = endwithx[num-1][i];if (sa.size() < min_len) {min_len = sa.size();min_idx = i;}}tgt = endwithx[num-1][min_idx];endwithx[num-1].erase(endwithx[num-1].begin()+min_idx, endwithx[num-1].begin()+min_idx+1);tgt.push_back(num);endwithx[num].push_back(tgt);}  }for (auto it = endwithx.begin(); it != endwithx.end(); it++) {for (auto sa : it->second) {if (sa.size() < 3)return false;}}return true;}
};

后来看了题解的写法，原来它记录的并不仅仅只是【以x-1为结尾的子列】，而是【以x-1为结尾且长度大于等于3的子列】。（这里注意因为x只会放到以x-1为结尾的子列后，因此第二个条件是都满足的）。也就是说，我的写法并不保证长度大于等于3，而是需要后面再判断（花费了更多时间）。而题解记录的就是长度大于等于3的子列，保证了合法性。

那么如何在放入时就确保子列长度大于等于3呢？答案是如果该元素x无法找到合适的子列插入时，它必须自己起头创造新的子列，那么又需要一个x+1和一个x+2。此时如果x+1和x+2的剩余量不足了，直接返回false即可。否则，消耗一个x、一个x+1和一个x+2，组成新的一个【以x+2为结尾的子列】，显然这个子列是合法的。

完整代码

class Solution {
public:bool isPossible(vector<int>& nums) {map<int, int> cnt;map<int, int> endwithx;for (auto num : nums) {if (cnt.find(num) == cnt.end())cnt[num] = 1;else    cnt[num]++;}for (auto num : nums) {if (cnt[num]) {if (endwithx.find(num-1) == endwithx.end() || endwithx[num-1] == 0) {// create an new array starting with num, num+1, num+2if (cnt[num+1] && cnt[num+2]) {cnt[num]--;cnt[num+1]--;cnt[num+2]--;if (endwithx.find(num+2) == endwithx.end())endwithx[num+2] = 1;elseendwithx[num+2]++;       }elsereturn false;}else {cnt[num]--;endwithx[num-1]--;endwithx[num]++;}}}return true;}
};