织梦网站变成手机站,微信网站入口,毕业册个人主页设计,2345网址大全文章目录 Tag题目来源解题思路方法一#xff1a;最长递增子序列 写在最后 Tag
【最长递增子序列】【数组】【2023-12-22】 题目来源
1671. 得到山形数组的最少删除次数 解题思路
方法一#xff1a;最长递增子序列
前后缀分解
根据前后缀思想#xff0c;以 nums[i] 为山… 文章目录 Tag题目来源解题思路方法一最长递增子序列 写在最后 Tag
【最长递增子序列】【数组】【2023-12-22】 题目来源
1671. 得到山形数组的最少删除次数 解题思路
方法一最长递增子序列
前后缀分解
根据前后缀思想以 nums[i] 为山顶的山形数组可以看成 nums[i] 左侧以其作为结尾的最长递增子序列我们记左侧的最长递增子序列的长度为 pre[i]拼接上 nums[i] 右侧以其作为结尾的最长递减子序列我们记右侧的最长递减子序列的长度为 suf[i]此时以 nums[i] 为山顶的山形数组长度为 p r e [ i ] s u f [ i ] − 1 pre[i] suf[i] - 1 pre[i]suf[i]−1 我们枚举所有的 nums[i]计算所有的最长山顶数组长度 maxLen最后需要删除的数组元素长度为 n - maxLen 即为最后需要返回的答案。
最长递增子序列
如何计算 pre 和 suf
pre 和 suf 的计算过程类似。先来看一下 pre 的计算。维护数组 prepre[i] 表示以 nums[i] 作为结尾的最长递增子序列的长度维护辅助数组 g表示以当前元素 nums[i] 结尾的最长递增子序列数组。
遍历数组 nums当前遍历的元素为 nums[i] 记为 x在数组 g 中使用二分查找找到第一个大于 x 的元素对应的位置为 it - g.begin() 1
更新 pre[i] it - g.begin() 1如果 x 不在 g 中则将 x 加入 g否则将 x 更新到 g 中相应的位置。
在 suf 的计算过程中我们从后往前遍历数组 nums就是找最长的递增子序列于是计算过程和 pre 的计算类似。 remark1因为山峰不可能在数组首和尾两个位置出现那么在遍历所有山峰的范围 [0, n-1] 时需要先做判断 pre[i] 2 suf[i] 2。 remark2可以先计算 suf然后一起计算 pre 和更新答案的留给读者自己实现。 算法
class Solution {
public:int minimumMountainRemovals(vectorint nums) {int n nums.size();vectorint pre(n), g;for (int i 0; i n; i) {int x nums[i];auto it lower_bound(g.begin(), g.end(), x);pre[i] it - g.begin() 1;if (it g.end()) {g.push_back(x);}else {*it x;}}vectorint suf(n);g.clear();for (int i n - 1; i 0; --i) {int x nums[i];auto it lower_bound(g.begin(), g.end(), x);suf[i] it - g.begin() 1;if (it g.end()) {g.push_back(x);}else {*it x;}}int mx 0;for (int i 1; i n - 1; i) {mx max(mx, pre[i] suf[i] - 1);}return n - mx;}
};复杂度分析
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)更新 pre 和 suf 的时间复杂度都为 O(nlogn)更新答案的时间复杂度为 O ( n ) O(n) O(n)。
空间复杂度 O ( n ) O(n) O(n)额外占用的空间为数组 pre、suf 和 g。空间复杂度 O ( n ) O(n) O(n)额外占用的空间为数组 pre、suf 和 g。 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
