LeetCode 659. 分割数组为连续子序列

摘要：
利用了贪心的思想。

题目

给你一个按升序排序的整数数组 $num$（可能包含重复数字），请你将它们分割成一个或多个子序列，其中每个子序列都由连续整数组成且长度至少为 $3$ 。
如果可以完成上述分割，则返回 $true$ ；否则，返回 $false$ 。

示例 1：

输入: [1,2,3,3,4,5]
输出: True
解释:
你可以分割出这样两个连续子序列 :
1, 2, 3
3, 4, 5

示例 2：

输入: [1,2,3,3,4,4,5,5]
输出: True
解释:
你可以分割出这样两个连续子序列 :
1, 2, 3, 4, 5
3, 4, 5

示例 3：

输入: [1,2,3,4,4,5]
输出: False

提示：

$1 <= nums.length <= 10000$

贪心

设想一个数组元素 $x$ ，我们有两种选择，一是将 $x$ 放到在以 $x - 1$ 结尾的子序列中，二是新建一个以 $x$ 开头的新序列。由于题干说明子序列长度至少为 $3$，利用贪心的思想，我们尽可能地将 $x$ 放到以 $x - 1$ 结尾的序列中去，除非该序列不存在。那么当该序列不存在时，我们不得已新建一个序列，同时判断有没有 $x + 1$ 和 $x + 2$ 存在于 $x$ 后面的数组中。如果都有，那么这个新序列将被建立，并且以 $x + 2$ 结尾，如果不存在那么整个数组将无法分割。
就这样，我们遍历整个数组，对于每一个数 $x$，要么加入到以 $x - 1$ 结尾的序列中，要么新建一个新序列并判断 $x + 1$ 和 $x + 2$ 有无剩余。所有的新序列都从长度为3开始，只要出现不满足初始化新序列的情况，直接 return false ，否则遍历完数组均无不满足新序列成立的情况，return true。

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        unordered_map<int, int> remain;
        unordered_map<int, int> endcount;
        for (auto x : nums) {
            remain[x] ++;
        }

        for (auto x : nums) {
            if (remain[x] > 0) {                                        // 因为之前在建立序列时，可能用到了x ，所以在遍历到x时，剩余数量可能不会大于等于1；
                if (endcount[x - 1] > 0) {                              // 存在以x-1结尾的序列
                    remain[x] --;
                    endcount[x - 1] --;
                    endcount[x] ++;
                } else {                                                // 没有以x-1结尾的序列，意味着需要开辟新的以x开始的序列
                    if (remain[x + 1] > 0 && remain[x + 2] > 0) {       // 要想构建以x开始的序列需要满足这个条件
                        remain[x] --;                                   // 构建新序列之后的状态
                        remain[x + 1] --;
                        remain[x + 2] --;
                        endcount[x + 2] ++;
                    } else {                                            // 无法以x开始生产一段满足最低标准的子序列
                        return false;
                    }
                }
            }
        }
        return true;
    }
};

现在证明为什么优先将 $x$ 放在以 $x-1$ 结尾的子序列中是最优选择。
将所有情况分为以下几种：

以 $x-1$ 结尾的子序列没有构成最低标准的子序列，那么如果不将 $x$ 放在 $x-1$ 结尾的子序列中，必然不满足条件，反之可能成功。这种情况显然将 $x$ 放在以 $x-1$ 结尾的子序列中是最优选择。
以 $x-1$ 结尾的子序列已构成满足条件的子序列，那么 $x$ 可以放也可以不放。
假设 $x$ 后面的数字可以构成以 $x$ 开始的最低标准子序列，那么放与不放都一样，无非是拼成了一段更长的子序列或分为两段子序列；
假设 $x$ 后面的数字不可以构成以 $x$ 开始的最低标准的子序列，那么如果不放的话，就以 $x$ 开始，那就必然失败，反之，如果放在了$x-1$ 后面，那么以 $x$ 后面的数开始一段新的子序列则可能成功。
这种情况显然将 $x$ 放在以 $x-1$ 结尾的子序列中也是最优选择。

原题链接： LeetCode 659. 分割数组为连续子序列