LeetCode334.递增的三元子序列：「序列DP & 二分」&「双向遍历DP」

浏览次数 : 次 2022-01-12

博文字数统计 : 2k字 | 阅读所需时长 : 8分

× 文章目录

1. LeetCode334.递增的三元子序列：「序列DP & 二分」&「双向遍历DP」

LeetCode334：递增的三元子序列
- 时间：2022-01-12
- 力扣难度：Medium
- 个人难度：Medium
- 数据结构：数组、LIS最长递增子序列
- 算法：动态规划、贪心、二分查找

LeetCode334.递增的三元子序列：「序列DP & 二分」&「双向遍历DP」

1. 题目描述

题目：原题链接
- 给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
- 如果存在这样的三元组下标 (i, j, k) 且满足 $i < j < k$，使得 $nums[i] < nums[j] < nums[k] $，返回 true ，否则，返回 false。
输入输出规范
- 输入：整数数组nums
- 输出：布尔值，表示是否存在递增三元子序列
输入输出示例
- 输入：nums = [2,1,5,0,4,6]
- 输出：true

2. 方法一：动态规划

思路：序列DP + 二分优化复杂度

本题是要判断给定的序列中是否存在长度为3的递增子序列，即是求序列的最长上升子序列(LIS)的长度是否大于3，类似于LC300最长递增子序列
一般而言，LIS问题属于序列DP问题，都可以通过动态规划的思想来解决，其DP三要素也非常明确
- DP数组：dp[i]表示以序列中的第 i 个元素结尾的最长上升子序列的长度
- 边界条件：dp[i]初始化为1
- 状态转移方程：if(nums[j] < nums[i]) dp[i] = Max(dp[i], dp[j] + 1) (j < i)

最长上升子序列的长度求解

两重遍历，外层dp[i]表示以 i 结尾的 LIS 的长度，并将最大值记录到 max 中
内层dp[j]是局部结果，j 的范围是 [0, i)，也可以是(i, n)，此时状态转移方程需要简单变一下

public int getLengthOfLIS(int[] nums) { 
    int n = nums.length;
    int max = 1;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i])
                dp[i] = Math.max(dp[j] + 1, dp[i]);
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}

题解：暴力动态规划，遍历过程中如果长度已经大于3直接返回true

public boolean increasingTriplet(int[] nums) {
       if(nums == null || nums.length < 3) return false;
       int n = nums.length;
       int[] dp = new int[n];
       Arrays.fill(dp, 1);
       for (int i = 0; i < n; i++) {
           for (int j = i + 1; j < n; j++) {
               if (nums[j] > nums[i])
                   dp[j] = Math.max(dp[i] + 1, dp[j]);
           }
           if(dp[i] >= 3) return true;
       }
       return false;
   }

复杂度分析：n 是数组的长度
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(n)$

3. 方法二：动态规划 + 二分查找

思路
- 方法一是LIS问题的常见思路，但是时间复杂度高，会发生TLE超时问题，此时要思考如何进行优化
- LIS问题的最优解：动态规划 & 二分
  - 首先分析如何确保LIS最长，通过贪心的思想可以发现，当每次向LIS末尾添加的元素是剩余元素中尽可能小的元素时，LIS的增长速率就相对更低
  - 举例说明下，假设LIS的末尾添加了元素A(A > B)，那么后续向LIS添加的元素一定大于A，即也会大于B，此时相当于B被遗漏了，LIS不是最长的，所以要添加尽可能小的元素
- DP数组
  - dp[i]表示指定的序列中，长度为 i **的最长上升子序列的最小结尾元素**
  - DP数组是单调上升的，可以通过二分的方式查找该数组中的值
- 边界条件：dp[0] = nums[0]，注意DP数组的个数是 n - 1 还是 n 个
- 状态转移方程
  - 遍历序列时，如果当前元素大于dp[i]，将其添加到DP数组末尾dp[i+1]
  - 如果当前元素小于等于dp[i]，通过二分的方式查找当前元素应该放到的DP数组中的位置dp[i - 1] < nums[i] < dp[i]，并更新
图解

题解：通过二分优化动态规划

// 方法二：LIS最优解：动态规划（贪心） + 二分
public boolean increasingTriplet2(int[] nums) {
    if (nums == null || nums.length < 3) return false;
    int n = nums.length;
    int[] dp = new int[n];
    dp[0] = nums[0];
    int len = 1;
    for (int i = 1; i < n; i++) {
        int num = nums[i];
        if (num > dp[len - 1]) {
            dp[len++] = num;
            if (len >= 3) return true;
            continue;
        }
        int left = 0, right = len - 1;
        while (left < right) {
            int mid = (right - left) / 2 + left;
            if (dp[mid] >= num) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        dp[right] = num;
        if (len >= 3) return true;
    }
    return false;
}

复杂度分析：n 是数组的长度
- 时间复杂度：$O(nlogn)$，遍历一次$O(n)$，内部嵌套二分查找$O(logn)$，整体$O(nlogn)$
- 空间复杂度：$O(n)$

4. 方法二优化：状态压缩

思路
- 首先总结下方法二的核心思想
  - 根据贪心的思想，维护一个动态规划DP数组来表示各个长度的LIS的末尾元素
  - 遍历序列的过程中，将大于末尾的元素直接添加，小于的二分查找并更新到DP数组中
- 虽然这已经是LIS类型题目的最优解法了，但是本题有一个特殊之处，那就是并不是求解LIS最大长度，而是只需要判断该长度是否大于等于3即可
- 因此，本题无需求解LIS最大长度，也不需要维护长度为 n 的DP数组，而仅需要维护两个变量：最小值、次小值即可
- 通过这种状态压缩的方式，不仅使得空间优化到$O(1)$常量空间，同时也无需进行二分查找，只需要判断序列中是否有大于这两个值的元素，时间优化到$O(n)$

题解：状态压缩优化

public boolean increasingTriplet(int[] nums) {
    if (nums == null || nums.length < 3) return false;
    int min = Integer.MAX_VALUE;
    int secondMin = Integer.MAX_VALUE;
    for (int num : nums) {
        if (num <= min) min = num;
        else if (num <= secondMin) secondMin = num;
        else return true;
    }
    return false;
}

复杂度分析：n 是数组的长度
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$

5. 方法三：动态规划

思路
- 此外，这里再介绍一种与LIS无关的方法，因为本题要求的是判断是否有递增三元子序列，所以可以使用类似LC42接雨水的解题方法
- 具体而言，由于要找递增三元组，就可以等价于在序列中寻找一个元素，该元素左侧存在一个小于它的值，右侧存在一个大于它的值
- 与接雨水一题不同的是，本题需要维护的左侧最小值和右侧最大值是数组，而不像接雨水中是单个数值
- 因此，维护两个DP数组，分别存放左侧的最小值和右侧的最大值，left[i] 表示序列 [0, i) 中的最小值，right[i] 表示 (i, n)中的最大值
- 遍历一次序列，计算出两个数组的每一个元素，如果两者满足left[i - 1] < nums[i] < right[i + 1]，表示找到了满足的三元组

题解：双向BFS

// 方法三：另类的动态规划
public boolean increasingTriplet(int[] nums) {
    if (nums == null || nums.length < 3) return false;
    int n = nums.length;
    // 左侧的最小值数组
    int[] leftMin = new int[n];
    leftMin[0] = nums[0];
    for (int i = 1; i < n; i++) {
        leftMin[i] = Math.min(leftMin[i - 1], nums[i]);
    }
    // 右侧的最大值数组
    int[] rightMax = new int[n];
    rightMax[n - 1] = nums[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        rightMax[i] = Math.max(rightMax[i + 1], nums[i]);
    }
    // 寻找递增三元子序列
    for (int i = 1; i < n - 1; i++) {
        if (leftMin[i - 1] < nums[i] && rightMax[i + 1] > nums[i]) return true;
    }
    return false;
}

复杂度分析：n 是数组的长度
- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$

本文作者： Chthollists
发布时间： 2022-01-12 16:35:19
最后更新： 2022-01-21 23:09:05
本文标题： LeetCode334.递增的三元子序列：「序列DP & 二分」&「双向遍历DP」
本文链接： https://chthollists.github.io/post/9ffc84e3.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！