【严格递增】2972统计移除递增子数组的数目 II

作者推荐

动态规划的时间复杂度优化

本文涉及知识点

严格递增子数组

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 <= 10⁵
1 <= nums[i] <= 10⁹

枚举子数组

本题想到了，很简单。如果能删除子数组[i1,j2]，需要三个条件？
一，[0,i1) 严格递增。
二，(j2,m_c) 严格递增
三，以下三个条件之一：a,0==i1。b,j2 == m_c 。c,s[i1-1] < s[j2+1]。

预处理

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[i+1]符合，i++。 $\rightarrow$ nums[0,i]符合。

代码

核心代码

class Solution {
public:
	long long incremovableSubarrayCount(vector<int>& 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 <= i+1); 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;
};

测试用例

template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{
	vector<int> 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 ) && ((j+1m_c )||(nums[j+1] > 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() + (j+1), 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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛