一个略有动态规划感觉的贪心题

<h1 id="leetcode-659-">LeetCode 659. 分割数组为连续子序列</h1>
<h2 id="heading">题目描述</h2>
给你一个按升序排序的整数数组<code>num</code>（可能包含重复数字），请你将它们分割成一个或多个长度为<code>3</code>的子序列，其中每个子序列都由连续整数组成。
如果可以完成上述分割，则返回<code>true</code>；否则，返回<code>false</code>。
示例一
输入: <code>[1,2,3,3,4,5]</code> 
输出: <code>True</code> 
解释: 
你可以分割出这样两个连续子序列 : 
<code>1, 2, 3</code> 
<code>3, 4, 5</code>
示例二
输入: <code>[1,2,3,3,4,4,5,5]</code> 
输出: <code>True</code> 
解释: 
你可以分割出这样两个连续子序列 : 
<code>1, 2, 3, 4, 5</code> 
<code>3, 4, 5</code>
示例三
输入: <code>[1,2,3,4,4,5]</code> 
输出: <code>False</code>
<h2 id="heading-1">题解</h2>
首先按照贪心的思路考虑该问题：
<ul>
<li>新的数应该尽可能把连续 2 个的数凑到满 3 个（如果凑不够，就要直接返回<code>false</code>）</li>
<li>当所有的 2 个数都凑到满 3 个后，尽可能把 1 个的数凑到满 2 个（如果凑不够，直接返回<code>false</code>)</li>
<li>当所有的 1 个都凑到 2 个后，把剩下的数尽可能和之前已经凑成一组（这样不会引入新的连续 1 个数，同时后面的连续的数也可以继续向后续）</li>
<li>只有还有多余的数必须单独成组，成为新的连续 1 个的</li>
</ul>
综上所述，只需要按照要求维护“连续 1 个”，“连续 2 个”，“连续 3 个以上”的个数即可
LeetCode 题解里有人给出了时间复杂度 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math>O(n)，空间复杂度 <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math>O(1) 的解法，相当于下面代码修改为一边计算个数，一边进行判断的情况。
<h2 id="heading-2">代码</h2>
<pre style="background-color:#fff">class Solution:
 def isPossible(self, nums: List[int]) -&gt; bool:
 if len(nums) == 0:
 return True
 count = {}
 for n in nums:
 count[n] = count.get(n, 0) + 1

 pre = -1
 l = [0, 0, 0, 0]
 for i in range(min(nums), max(nums) + 1):
 if pre == -1:
 # 没有前一个数
 if count.get(i, 0) &gt; 0:
 # 当前数有值，则更新为当前数
 l[1] = count[i]
 l[2] = 0
 l[3] = 0
 pre = i
 else:
 continue
 else:
 if count.get(i, 0) == 0:
 # 存在前一个数，同时当前数不存在
 if l[1] != 0 or l[2] != 0:
 # 还有没凑够 3 个的数
 return False
 else:
 # 全部都凑够 3 个，从新开始
 l[3] = 0
 pre = -1
 continue
 else:
 c = count[i]
 temp = l[3]
 # 优先凑 3 个
 if c &gt;= l[2]:
 # 足够把 2 个的都凑成 3 个
 c -= l[2]
 l[3] = l[2]
 if c &gt;= l[1]:
 # 足够把所有 1 个的凑成 2 个
 c -= l[1]
 l[2] = l[1]
 if c &gt; temp:
 # 剩下的都补给原本就有 3 个的仍有剩余
 l[1] = c - temp
 l[3] += temp
 else:
 # 剩下的都补给原本就有 3 个的
 l[1] = 0
 l[3] += c
 else:
 # 只能把部分 1 个凑成 2 个
 return False
 else:
 # 只能把部分 2 个凑成 3 个
 return False
 return l[1] == 0 and l[2] == 0
</pre>