题目描述：
给你一个按 非递减顺序 排列的整数数组 nums 。
请你判断是否能在将 nums 分割成 一个或多个子序列 的同时满足下述 两个 条件：
- 每个子序列都是一个 连续递增序列（即，每个整数 恰好 比前一个整数大 1 ）。
- 所有子序列的长度 至少 为
3 。
如果可以分割 nums 并满足上述条件，则返回 true ；否则，返回 false 。
数据范围：
$1\le nums.len \le 10^4; -1000 \le nums[i] \le 1000$
nums按照非递减顺序排列
题解：
贪心的维护更长的序列，每次遇到一个数字 $x$ ，贪心的接到 $x - 1$ 后面，如果找不到 $x - 1$ 的话再考虑开一个新的序列 $x, x + 1, x + 2$ 。如果不能构成一个长度至少为 $3$ 的序列，则直接返回 false。
因此需要使用哈希表记录后面还剩余的 $x$ 的数量，同时需要使用一个哈希表记录前面已经有多少以 $x - 1$ 结尾的长度大于等于 $3$ 的序列。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
bool isPossible(vector<int> &nums)
{
int n = nums.size();
unordered_map<int, int> cnt;
unordered_map<int, int> endXNum;
for (auto &x : nums)
cnt[x]++;
for (int i = 0; i < n; ++i)
{
if (cnt[nums[i]] == 0)
continue;
int x = nums[i];
if (endXNum.count(x - 1) && endXNum[x - 1] != 0)
{
endXNum[x - 1]--;
endXNum[x]++;
cnt[x]--;
}
else
{
bool flag = true;
for (int j = 1; j < 3; ++j)
{
if (cnt[x + j] == 0)
{
flag = false;
break;
}
}
endXNum[x + 2]++;
for (int j = 0; j < 3; ++j)
{
cnt[x + j]--;
}
if (!flag)
return false;
}
}
return true;
}
};
|