北京网站建设比较好的公司,网站前台的模块,七牛镜像存储 wordpress,实木餐桌椅网站建设作者推荐
动态规划的时间复杂度优化
本文涉及知识点
严格递增 子数组
LeetCode2972. 统计移除递增子数组的数目 II
给你一个下标从 0 开始的 正 整数数组 nums 。 如果 nums 的一个子数组满足#xff1a;移除这个子数组后剩余元素 严格递增 #xff0c;那么我们称这个子…作者推荐
动态规划的时间复杂度优化
本文涉及知识点
严格递增 子数组
LeetCode2972. 统计移除递增子数组的数目 II
给你一个下标从 0 开始的 正 整数数组 nums 。 如果 nums 的一个子数组满足移除这个子数组后剩余元素 严格递增 那么我们称这个子数组为 移除递增 子数组。比方说[5, 3, 4, 6, 7] 中的 [3, 4] 是一个移除递增子数组因为移除该子数组后[5, 3, 4, 6, 7] 变为 [5, 6, 7] 是严格递增的。 请你返回 nums 中 移除递增 子数组的总数目。 注意 剩余元素为空的数组也视为是递增的。 子数组 指的是一个数组中一段连续的元素序列。 示例 1 输入nums [1,2,3,4] 输出10 解释10 个移除递增子数组分别为[1], [2], [3], [4], [1,2], [2,3], [3,4], [1,2,3], [2,3,4] 和 [1,2,3,4]。移除任意一个子数组后剩余元素都是递增的。注意空数组不是移除递增子数组。 示例 2 输入nums [6,5,7,8] 输出7 解释7 个移除递增子数组分别为[5], [6], [5,7], [6,5], [5,7,8], [6,5,7] 和 [6,5,7,8] 。 nums 中只有这 7 个移除递增子数组。 示例 3 输入nums [8,7,6,6] 输出3 解释3 个移除递增子数组分别为[8,7,6], [7,6,6] 和 [8,7,6,6] 。注意 [8,7] 不是移除递增子数组因为移除 [8,7] 后 nums 变为 [6,6] 它不是严格递增的。 提示 1 nums.length 105 1 nums[i] 109
枚举子数组
本题想到了很简单。如果能删除子数组[i1,j2]需要三个条件 一[0,i1) 严格递增。 二(j2,m_c) 严格递增 三以下三个条件之一a,0i1。b,j2 m_c 。c,s[i1-1] s[j21]。
预处理
nums[0,i]是最长严格递增前缀。nums[j,m_c)是最长严格递增后缀。 令j1是nums[j,m_c)中第一个大于nums[i1]的下标。则j2的最小值为j1-1。 大于j1值全部是合法的j2。故合法的j2的数量m_c-(j1-1)。
小结
以严格递增前缀为例 nums[0,0]一定符合nums[i]如果符合则i。 → \rightarrow → nums[0,i)符合。 nums[0,0]一定符合如果nums[i1]符合i。 → \rightarrow → nums[0,i]符合。
代码
核心代码
class Solution {
public:long long incremovableSubarrayCount(vectorint nums) {m_c nums.size();int i 0, j m_c - 1;for (; (i 1 m_c) (nums[i] nums[i 1]); i);//nums[0,i]是严格递增for (; (j - 1 0) (nums[j - 1] nums[j]); j--);//nuns[j,m_c)是严格递增int iNeedDel j - i;if (iNeedDel 0 ){//nums[0,m_c)严格递增return (m_c 1) * m_c / 2;}//枚举删除[0,x]long long llCnt m_c - (j-1);for (int i1 1; (i1 m_c)(i1 i1); i1){//删除子数组[i,x]int j1 std::upper_bound(nums.begin() j, nums.end(), nums[i1-1]) - nums.begin();llCnt m_c - (j1 - 1);}return llCnt;}int m_c;
};测试用例
templateclass T,class T2
void Assert(const T t1, const T2 t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){Assert(v1[i], v2[i]);}}int main()
{vectorint nums;{Solution sln;nums { 6,5,7,8 };auto res sln.incremovableSubarrayCount(nums);Assert(7, res);}{Solution sln;nums { 1,2,3,4 };auto res sln.incremovableSubarrayCount(nums);Assert(10, res);}{Solution sln;nums { 8,7,6,6 };auto res sln.incremovableSubarrayCount(nums);Assert(3, res);}
}第二版
class Solution { public: long long incremovableSubarrayCount(vector nums) { m_c nums.size(); int i 0, j m_c - 1; for (; (i m_c) ((0i ) || (nums[i-1] nums[i])); i);//nums[0,i)是最长前缀 for (; (j 0 ) ((j1m_c )||(nums[j1] nums[j ])); j–);//nums(j,m_c)是最长后缀 if (j 0) { return (m_c 1) * m_c / 2; } long long llRet m_c - j; for (int i1 1; (i1 i)(i1 m_c); i1) { auto j1 std::upper_bound(nums.begin() (j1), nums.end(), nums[i1-1])-nums.begin(); llRet m_c - (j1 - 1); } return llRet; } int m_c; };
扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。 https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程 https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
