北京平台网站建设报价,东莞清溪网站建设,怎样学习做网站,短剧小程序开发费用2023.12.22 题目来源我的题解方法一 前后缀分解最长递增子序列 题目来源
力扣每日一题#xff1b;题序#xff1a;1671
我的题解
方法一 前后缀分解最长递增子序列
#xff08;参照题解中的#xff1a;灵茶山艾府的解法#xff09; 要想删除次数最少#xff0c;山形数… 2023.12.22 题目来源我的题解方法一 前后缀分解最长递增子序列 题目来源
力扣每日一题题序1671
我的题解
方法一 前后缀分解最长递增子序列
参照题解中的灵茶山艾府的解法 要想删除次数最少山形数组的子序列长度越长越好。至于最终的最长是多少这个可以将每一个位置都当做山峰来枚举计算每个位置的山形子序列的最长长度。 山形子序列是一个严格递增的子序列严格递减的子序列 定义pre[i]表示子序列最后一个数是nums[i]的最长严格递增子序列的长度定义suf[i]表示子序列第一个数是nums[i]的最长严格递减子序列的长度 这道题与昨日的山状数组有所不同就是眼球山峰左右两侧必须有数字所以pre[i]2并且suf[i]2。因而得到以nums[i]为山顶的最长山状子序列的长度为pre[i]suf[i]-1。 计算suf相当于求从右到左遍历nums求最长严格递增子序列在计算时为了简便采用反转数组来实现。同理计算pre相当于从左到右遍历nums求最长递增子序列。求最长严格递增子序列的方法有动态规划和二分查找两种这里采用二分查找。 最终结果数组长度-山形子序列的最长长度 时间复杂度O(nlogn) 空间复杂度O(n) public int minimumMountainRemovals(int[] nums) {int n nums.length;int[] suf new int[n];ListInteger g new ArrayList();for (int i n - 1; i 0; i--) {int x nums[i];int j lowerBound(g, x);if (j g.size()) {g.add(x);} else {g.set(j, x);}suf[i] j 1; // 从 nums[i] 开始的最长严格递减子序列的长度}int mx 0;g.clear();for (int i 0; i n - 1; i) {int x nums[i];int j lowerBound(g, x);if (j g.size()) {g.add(x);} else {g.set(j, x);}int pre j 1; // 在 nums[i] 结束的最长严格递增子序列的长度if (pre 2 suf[i] 2) {mx Math.max(mx, pre suf[i] - 1); // 减去重复的 nums[i]}}return n - mx;}private int lowerBound(ListInteger g, int target) {int left -1, right g.size(); // 开区间 (left, right)while (left 1 right) { // 区间不为空// 循环不变量// nums[left] target// nums[right] targetint mid (left right) 1;if (g.get(mid) target) {left mid; // 范围缩小到 (mid, right)} else {right mid; // 范围缩小到 (left, mid)}}return right; // 或者 left1}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
