双指针，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 = 0
        while i + 1 < n and nums[i] < nums[i + 1]:
            i += 1

        if i == n - 1:
            return n * (n + 1) // 2
        
        j = n - 1
        res = i + 2
        while j == n - 1 or nums[j] < nums[j + 1]:
            while ~i and nums[i] >= nums[j]:
                i -= 1
            res += i + 2
            j -= 1
        return 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;
    }
}