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
