双指针，LeetCode 2972. 统计移除递增子数组的数目 II

一、题目

1、题目描述

给你一个下标从 0 开始的 正 整数数组 nums 。

如果 nums 的一个子数组满足：移除这个子数组后剩余元素 严格递增 ，那么我们称这个子数组为 移除递增 子数组。比方说，[5, 3, 4, 6, 7] 中的 [3, 4] 是一个移除递增子数组，因为移除该子数组后，[5, 3, 4, 6, 7] 变为 [5, 6, 7] ，是严格递增的。

请你返回 nums 中 移除递增 子数组的总数目。

注意 ，剩余元素为空的数组也视为是递增的。

子数组 指的是一个数组中一段连续的元素序列。

2、接口描述

python3

 ​

class Solution:def incremovableSubarrayCount(self, nums: List[int]) -> int:

cpp

 ​

class Solution {
public:long long incremovableSubarrayCount(vector<int>& nums) {}
};

C#

 ​

public class Solution {public long IncremovableSubarrayCount(int[] nums) {}
}

3、原题链接

2972. 统计移除递增子数组的数目 II

---

二、解题报告

1、思路分析

考虑我们要的递增数组是一个前缀一个后缀拼接的，且前缀后缀可以为空

对于本身就是递增数组的数组，答案就是(n + 1) * n / 2，直接特判

否则，我们考虑最长递增前缀的末尾下标为i，那么只保留前缀的结果有i + 2个（注意可以为空）

然后考虑可以保留后缀的结果

对于每个j（满足num[j, ..., n - 1]递增），我们可以指针后移或者二分得到最靠右的nums[i]，其中nums[i] < nums[j]，那么含后缀nums[j, ..., n - 1]的答案数目取决于我们保留前缀的数目，显然是i  +2

那么我们的做法就是：

求最长递增前缀

双指针计算贡献

2、复杂度

时间复杂度： O(N)空间复杂度：O(N)

3、代码详解

python3

 ​

class Solution:def incremovableSubarrayCount(self, nums: List[int]) -> int:n = len(nums)i = 0while i + 1 < n and nums[i] < nums[i + 1]:i += 1if i == n - 1:return n * (n + 1) // 2j = n - 1res = i + 2while j == n - 1 or nums[j] < nums[j + 1]:while ~i and nums[i] >= nums[j]:i -= 1res += i + 2j -= 1return res

cpp

 ​

class Solution {
public:long long incremovableSubarrayCount(vector<int>& nums) {int n = nums.size();int i = 0;while (i + 1 < n && nums[i] < nums[i + 1]) ++ i;if (i + 1 == n) return (n + 1LL) * n / 2;long long res = i + 2;int j = n - 1;while (j == n - 1 || nums[j] < nums[j + 1]) {while (~i && nums[i] >= nums[j]) -- i;res += i + 2;-- j;}return res;}
};

C#

 ​

public class Solution {public long IncremovableSubarrayCount(int[] nums) {int n = nums.Length;int i = 0;while (i + 1 < n && nums[i] < nums[i + 1]) ++ i;if (i + 1 == n) return (n + 1L) * n / 2;long res = i + 2;int j = n - 1;while (j == n - 1 || nums[j] < nums[j + 1]) {while (i >= 0 && nums[i] >= nums[j]) -- i;res += i + 2;-- j;}return res;}
}