LeetCode 491 - Increasing Subsequences｜BIG MEOW

LeetCode 491 - Increasing Subsequences｜BIG MEOW

给定一个数组，返回所有可能的非严格增序子集，子集至少有两个元素。数组中有重复元素。

举例:
Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

思路

动态规划解法。遍历数组 nums 。用一个 map 来存储 已经出现过的值及其上次出现的位置。

nums[i] 的结果集等于之前所有结果集 res[i - 1] 加上 res[i - 1] 中所有 List 加上 nums[i] （如果 nums[i] 大于最后的数）再加上:

• 若 nums[i] 第一次出现，nums[i] 与 map 中所有 key 的对子。
• 若 map 中已存在 nums[i] ，遍历上次位置 last 到这次位置 curr，若某个值 nums[j] 首次出现的位置 i 比 last 小，说明这个值在上次 nums[i] 以后才有，应该将 (nums[j], nums[i]) 加入集合 res 。
  最后将 (nums[i], i) 存入 map

本来是用一个 List<List<List<Integer>>> 作为 dp 来做，写完之后发现只要记录一下上一次加的最后一个就好了。

用 List 超时了，应该是中间判断的时间花了太久，干脆先用 set 存，最后转到 List 里，过了。以为考的就是重复时候的条件，辣鸡。

Read full article from LeetCode 491 - Increasing Subsequences｜BIG MEOW