LeetCode刷题实战491：递增子序列-技术圈

LeetCode刷题实战491：递增子序列

共 1468字，需浏览 3分钟

· 2022-01-09

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 递增子序列，我们先来看题面：

https://leetcode-cn.com/problems/increasing-subsequences/

Given an integer array nums, return all the different possible increasing subsequences of the given array with at least two elements. You may return the answer in any order.

The given array may contain duplicates, and two equal integers should also be considered a special case of increasing sequence.

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素。你可以按任意顺序返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例

示例 1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

输入：nums = [4,4,3,2,1]
输出：[[4,4]]

解题

https://www.cnblogs.com/kexinxin/p/10372504.html

利用递归的思想，维护一个栈，将每次找到的比当前栈顶大的数，然后入栈，将更新过后的栈扔进递归函数，然后更新查找的初始位置即从当前的位置后一个位置开始查找。递归函数结束后，取出栈顶，进入下个循环，这样将所有元素都作为栈底元素遍历一遍。

public class Solution {
    public List> findSubsequences(int[] nums) {
        Set> res = new HashSet>();
        helper(res, new ArrayList(), nums, 0);
        return new ArrayList>(res);
    }

    private void helper(Set> res, List subList, int[] nums, int start) {
        if (subList.size() >= 2) {
            res.add(new ArrayList(subList));
        }
        for (int i = start; i < nums.length; i++) {
            if (subList.size() == 0 || subList.get(subList.size() - 1) <= nums[i]) {
                subList.add(nums[i]);
                helper(res, subList, nums, i + 1);
                subList.remove(subList.size() - 1);
            }
        }
    }
}