class072 最长递增子序列问题与扩展【算法】-阿里云开发者社区

class072 最长递增子序列问题与扩展【算法】

code1 300. 最长递增子序列

// 最长递增子序列和最长不下降子序列

// 给定一个整数数组nums

// 找到其中最长严格递增子序列长度、最长不下降子序列长度

// 测试链接 : https://leetcode.cn/problems/longest-increasing-subsequence/

dp[i]：以i位置作结尾的最长递增子序列长度

返回Max(dp[…])

优化

ends[i]：目前所有长度为i+1的递增子序列的最小结尾

返回len

code1 动态规划

code2 优化

package class072;
// 最长递增子序列和最长不下降子序列
// 给定一个整数数组nums
// 找到其中最长严格递增子序列长度、最长不下降子序列长度
// 测试链接 : https://leetcode.cn/problems/longest-increasing-subsequence/
public class Code01_LongestIncreasingSubsequence {
  // 普通解法的动态规划
  // 时间复杂度O(n^2)，数组稍大就会超时
  public static int lengthOfLIS1(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    int ans = 0;
    for (int i = 0; i < n; i++) {
      dp[i] = 1;
      for (int j = 0; j < i; j++) {
        if (nums[j] < nums[i]) {
          dp[i] = Math.max(dp[i], dp[j] + 1);
        }
      }
      ans = Math.max(ans, dp[i]);
    }
    return ans;
  }
  // 最优解
  // 时间复杂度O(n * logn)
  public static int lengthOfLIS2(int[] nums) {
    int n = nums.length;
    int[] ends = new int[n];
    // len表示ends数组目前的有效区长度
    // ends[0...len-1]是有效区，有效区内的数字一定严格升序
    int len = 0;
    for (int i = 0, find; i < n; i++) {
      find = bs1(ends, len, nums[i]);
      if (find == -1) {
        ends[len++] = nums[i];
      } else {
        ends[find] = nums[i];
      }
    }
    return len;
  }
  // "最长递增子序列"使用如下二分搜索 :
  // ends[0...len-1]是严格升序的，找到>=num的最左位置
  // 如果不存在返回-1
  public static int bs1(int[] ends, int len, int num) {
    int l = 0, r = len - 1, m, ans = -1;
    while (l <= r) {
      m = (l + r) / 2;
      if (ends[m] >= num) {
        ans = m;
        r = m - 1;
      } else {
        l = m + 1;
      }
    }
    return ans;
  }
  // 如果求最长不下降子序列，那么使用如下的二分搜索 :
  // ends[0...len-1]是不降序的
  // 在其中找到>num的最左位置，如果不存在返回-1
  // 如果求最长不下降子序列，就在lengthOfLIS中把bs1方法换成bs2方法
  // 已经用对数器验证了，是正确的
  public static int bs2(int[] ends, int len, int num) {
    int l = 0, r = len - 1, m, ans = -1;
    while (l <= r) {
      m = (l + r) / 2;
      if (ends[m] > num) {
        ans = m;
        r = m - 1;
      } else {
        l = m + 1;
      }
    }
    return ans;
  }
}

code2 354. 俄罗斯套娃信封问题

// 俄罗斯套娃信封问题

// 给你一个二维整数数组envelopes ，其中envelopes[i]=[wi, hi]

// 表示第 i 个信封的宽度和高度

// 当另一个信封的宽度和高度都比这个信封大的时候

// 这个信封就可以放进另一个信封里，如同俄罗斯套娃一样

// 请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封

// 即可以把一个信封放到另一个信封里面，注意不允许旋转信封

// 测试链接 : https://leetcode.cn/problems/russian-doll-envelopes/

排序策略:宽度从小到大；宽度一样，高度从大到小

构成高度数组，求最长递增子序列的长度

package class072;
import java.util.Arrays;
// 俄罗斯套娃信封问题
// 给你一个二维整数数组envelopes ，其中envelopes[i]=[wi, hi]
// 表示第 i 个信封的宽度和高度
// 当另一个信封的宽度和高度都比这个信封大的时候
// 这个信封就可以放进另一个信封里，如同俄罗斯套娃一样
// 请计算 最多能有多少个信封能组成一组“俄罗斯套娃”信封
// 即可以把一个信封放到另一个信封里面，注意不允许旋转信封
// 测试链接 : https://leetcode.cn/problems/russian-doll-envelopes/
public class Code02_RussianDollEnvelopes {
  public static int maxEnvelopes(int[][] envelopes) {
    int n = envelopes.length;
    // 排序策略:
    // 宽度从小到大
    // 宽度一样，高度从大到小
    Arrays.sort(envelopes, (a, b) -> a[0] != b[0] ? (a[0] - b[0]) : (b[1] - a[1]));
    int[] ends = new int[n];
    int len = 0;
    for (int i = 0, find, num; i < n; i++) {
      num = envelopes[i][1];
      find = bs(ends, len, num);
      if (find == -1) {
        ends[len++] = num;
      } else {
        ends[find] = num;
      }
    }
    return len;
  }
  public static int bs(int[] ends, int len, int num) {
    int l = 0, r = len - 1, m, ans = -1;
    while (l <= r) {
      m = (l + r) / 2;
      if (ends[m] >= num) {
        ans = m;
        r = m - 1;
      } else {
        l = m + 1;
      }
    }
    return ans;
  }
}

code3 2111. 使数组 K 递增的最少操作次数

// 使数组K递增的最少操作次数

// 给你一个下标从0开始包含n个正整数的数组arr，和一个正整数k

// 如果对于每个满足 k <= i <= n-1 的下标 i

// 都有 arr[i-k] <= arr[i] ，那么称 arr 是K递增的

// 每一次操作中，你可以选择一个下标i并将arr[i]改成任意正整数

// 请你返回对于给定的 k ，使数组变成K递增的最少操作次数

// 测试链接 : https://leetcode.cn/problems/minimum-operations-to-make-the-array-k-increasing/

把每一组分出来

求出每一组的最长不下降子序列的长度，

修改长度就是总长度减去最长不下降子序列的长度

每一组的修改长度求和即为答案

package class072;
// 使数组K递增的最少操作次数
// 给你一个下标从0开始包含n个正整数的数组arr，和一个正整数k
// 如果对于每个满足 k <= i <= n-1 的下标 i
// 都有 arr[i-k] <= arr[i] ，那么称 arr 是K递增的
// 每一次操作中，你可以选择一个下标i并将arr[i]改成任意正整数
// 请你返回对于给定的 k ，使数组变成K递增的最少操作次数
// 测试链接 : https://leetcode.cn/problems/minimum-operations-to-make-the-array-k-increasing/
public class Code03_MinimumOperationsToMakeArraykIncreasing {
  public static int MAXN = 100001;
  public static int[] nums = new int[MAXN];
  public static int[] ends = new int[MAXN];
  public static int kIncreasing(int[] arr, int k) {
    int n = arr.length;
    int ans = 0;
    for (int i = 0, size; i < k; i++) {
      size = 0;
      // 把每一组的数字放入容器
      for (int j = i; j < n; j += k) {
        nums[size++] = arr[j];
      }
      // 当前组长度 - 当前组最长不下降子序列长度 = 当前组至少需要修改的数字个数
      ans += size - lengthOfNoDecreasing(size);
    }
    return ans;
  }
  // nums[0...size-1]中的最长不下降子序列长度
  public static int lengthOfNoDecreasing(int size) {
    int len = 0;
    for (int i = 0, find; i < size; i++) {
      find = bs(len, nums[i]);
      if (find == -1) {
        ends[len++] = nums[i];
      } else {
        ends[find] = nums[i];
      }
    }
    return len;
  }
  public static int bs(int len, int num) {
    int l = 0, r = len - 1, m, ans = -1;
    while (l <= r) {
      m = (l + r) / 2;
      if (num < ends[m]) {
        ans = m;
        r = m - 1;
      } else {
        l = m + 1;
      }
    }
    return ans;
  }
}

code4 646. 最长数对链

// 最长数对链

// 给你一个由n个数对组成的数对数组pairs

// 其中 pairs[i] = [lefti, righti] 且 lefti < righti

// 现在，我们定义一种跟随关系，当且仅当 b < c 时

// 数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面

// 我们用这种形式来构造数对链

// 找出并返回能够形成的最长数对链的长度

// 测试链接 : https://leetcode.cn/problems/maximum-length-of-pair-chain/

按开头有序

ends数组，放数对的最小结尾，查要查数对的开头，第一个比它大的，再更新最小结尾。

package class072;
import java.util.Arrays;
// 最长数对链
// 给你一个由n个数对组成的数对数组pairs
// 其中 pairs[i] = [lefti, righti] 且 lefti < righti
// 现在，我们定义一种 跟随 关系，当且仅当 b < c 时
// 数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面
// 我们用这种形式来构造 数对链
// 找出并返回能够形成的最长数对链的长度
// 测试链接 : https://leetcode.cn/problems/maximum-length-of-pair-chain/
public class Code04_MaximumLengthOfPairChain {
  public static int findLongestChain(int[][] pairs) {
    int n = pairs.length;
    // 数对根据开始位置排序，从小到大
    // 结束位置无所谓！
    Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
    // 结尾的数值
    int[] ends = new int[n];
    int len = 0;
    for (int[] pair : pairs) {
      int find = bs(ends, len, pair[0]);
      if (find == -1) {
        ends[len++] = pair[1];
      } else {
        ends[find] = Math.min(ends[find], pair[1]);
      }
    }
    return len;
  }
  // >= num最左位置
  public static int bs(int[] ends, int len, int num) {
    int l = 0, r = len - 1, m, ans = -1;
    while (l <= r) {
      m = (l + r) / 2;
      if (ends[m] >= num) {
        ans = m;
        r = m - 1;
      } else {
        l = m + 1;
      }
    }
    return ans;
  }
}

code5 P8776 [蓝桥杯 2022 省 A] 最长不下降子序列

// 有一次修改机会的最长不下降子序列

// 给定一个长度为n的数组arr，和一个整数k

// 只有一次机会可以将其中连续的k个数全修改成任意一个值

// 这次机会你可以用也可以不用，请返回最长不下降子序列长度

// 1 <= k, n <= 10^5

// 1 <= arr[i] <= 10^6

// 测试链接 : https://www.luogu.com.cn/problem/P8776

// 请同学们务必参考如下代码中关于输入、输出的处理

// 这是输入输出处理效率很高的写法

// 提交以下的所有代码，并把主类名改成"Main"，可以直接通过

[k个z]   z
0       i         j
最后小于z的  +k    +包含j位置的
不下降子序列的长度     不下降子序列的长度

包含j位置的不下降子序列的长度等同于求出n-1…j的最长不上升子序列

ends存放最大结尾

673. 最长递增子序列的个数

给定一个未排序的整数数组 nums ，返回最长递增子序列的个数。

测试链接：https://leetcode.cn/problems/number-of-longest-increasing-subsequence/

重剑无锋，大巧不工

package class072;
// 有一次修改机会的最长不下降子序列
// 给定一个长度为n的数组arr，和一个整数k
// 只有一次机会可以将其中连续的k个数全修改成任意一个值
// 这次机会你可以用也可以不用，请返回最长不下降子序列长度
// 1 <= k, n <= 10^5
// 1 <= arr[i] <= 10^6
// 测试链接 : https://www.luogu.com.cn/problem/P8776
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的所有代码，并把主类名改成"Main"，可以直接通过
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
public class Code05_LongestNoDecreaseModifyKSubarray {
  public static int MAXN = 100001;
  public static int[] arr = new int[MAXN];
  public static int[] right = new int[MAXN];
  public static int[] ends = new int[MAXN];
  public static int n, k;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StreamTokenizer in = new StreamTokenizer(br);
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while (in.nextToken() != StreamTokenizer.TT_EOF) {
      n = (int) in.nval;
      in.nextToken();
      k = (int) (in.nval);
      for (int i = 0; i < n; i++) {
        in.nextToken();
        arr[i] = (int) in.nval;
      }
      if (k >= n) {
        out.println(n);
      } else {
        out.println(compute());
      }
    }
    out.flush();
    out.close();
    br.close();
  }
  public static int compute() {
    right();
    int len = 0;
    int ans = 0;
    for (int i = 0, j = k, find, left; j < n; i++, j++) {
      find = bs2(len, arr[j]);
      left = find == -1 ? len : find;
      ans = Math.max(ans, left + k + right[j]);
      find = bs2(len, arr[i]);
      if (find == -1) {
        ends[len++] = arr[i];
      } else {
        ends[find] = arr[i];
      }
    }
    ans = Math.max(ans, len + k);
    return ans;
  }
  // 生成辅助数组right
  // right[j] :
  // 一定以arr[j]做开头的情况下，arr[j...]上最长不下降子序列长度是多少
  // 关键逻辑 :
  // 一定以arr[i]做开头的情况下，arr[i...]上最长不下降子序列
  // 就是！从n-1出发来看(从右往左遍历)，以arr[i]做结尾的情况下的最长不上升子序列
  public static void right() {
    int len = 0;
    for (int i = n - 1, find; i >= 0; i--) {
      find = bs1(len, arr[i]);
      if (find == -1) {
        ends[len++] = arr[i];
        right[i] = len;
      } else {
        ends[find] = arr[i];
        right[i] = find + 1;
      }
    }
  }
  // 求最长不上升子序列长度的二分
  // ends[0...len-1]是降序的，找到<num的最左位置
  // 不存在返回-1
  public static int bs1(int len, int num) {
    int l = 0, r = len - 1, m, ans = -1;
    while (l <= r) {
      m = (l + r) / 2;
      if (ends[m] < num) {
        ans = m;
        r = m - 1;
      } else {
        l = m + 1;
      }
    }
    return ans;
  }
  // 求最长不下降子序列长度的二分
  // ends[0...len-1]是升序的，找到>num的最左位置
  // 不存在返回-1
  public static int bs2(int len, int num) {
    int l = 0, r = len - 1, m, ans = -1;
    while (l <= r) {
      m = (l + r) / 2;
      if (ends[m] > num) {
        ans = m;
        r = m - 1;
      } else {
        l = m + 1;
      }
    }
    return ans;
  }
}

2023-11-09 20:58:41

class072 最长递增子序列问题与扩展【算法】