0491. Non-decreasing Subsequences¶
题目信息¶
- 题号:
0491
- 难度:
Medium
- 主题:
子序列、非递减、长度至少二、结果去重
- 原题:
- 重点:
保持原下标顺序但可跳过元素、后项可等于前项、相同数值序列只返回一次、结果顺序不限
题目重述¶
给定整数数组 nums,返回其中所有不同的非递减子序列。每个子序列长度至少为 2,并且相邻所选元素满足后一个值大于或等于前一个值。
子序列可以跳过原数组中的元素,但保留元素的下标顺序不能改变。由不同下标选择产生相同数值序列时,结果中只能保留一个副本。nums.length 位于 [1, 15],每个元素位于 [-100, 100],结果顺序不限。
自建示例¶
重复值会产生重复下标选择:
输入:nums = [1,2,1,2]
输出可包含:[[1,1], [1,2], [2,2], [1,1,2], [1,2,2]]
解释:[1,2] 可以由多个不同下标组合得到,但作为数值序列只能返回一次;列出的五种是全部不同合法结果,顺序不限。
只有一条合法子序列:
输入:nums = [3,3,2]
输出:[[3,3]]
解释:前两个 3 构成非递减子序列,任何包含末尾 2 的长度至少为 2 的子序列都会下降。
按递归层去重并保持下标递增¶
回溯参数 start 表示下一次只能从哪个下标之后选择,因而自动保证子序列顺序。若候选值不小于路径末尾,就可以加入路径;路径长度达到 2 时记录一份结果,然后继续向后扩展。
同一递归层中,数值相同的候选会产生相同的后续数值序列,只保留第一次尝试。这个集合必须在每层递归重新建立:同一个值在不同深度仍可能形成合法的不同长度序列。
C++ 实现¶
class Solution {
std::vector<int> path;
std::vector<std::vector<int>> result;
void search(const std::vector<int>& nums, int start) {
if (path.size() >= 2) result.push_back(path);
std::unordered_set<int> used;
for (int i = start; i < static_cast<int>(nums.size()); ++i) {
if (used.count(nums[i])) continue;
used.insert(nums[i]);
if (!path.empty() && nums[i] < path.back()) continue;
path.push_back(nums[i]);
search(nums, i + 1);
path.pop_back();
}
}
public:
std::vector<std::vector<int>> findSubsequences(
std::vector<int>& nums) {
path.clear();
result.clear();
search(nums, 0);
return result;
}
};
代码分析¶
start 只向右移动,保证每条路径是原数组的子序列;层内去重只删除相同值、相同前缀下的重复分支,不会删除跨层的合法序列。最坏时间复杂度与不同子序列数量同阶,额外空间为 O(n) 的递归路径和去重集合(不计输出)。