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

难度: Hard

给你一个下标从 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⁹

Submission

运行时间: 58 ms

内存: 30.3 MB

class Solution:
    #枚举要删除的数组的左端点，看右端点有多少个
    def incremovableSubarrayCount(self, nums: List[int]) -> int:
        n = len(nums)
        r = n - 1
        ans = 0
        while r > 0 and nums[r - 1] < nums[r]:
            r -= 1
        ans += n - r + (1 if r > 0 else 0)
        l = 0
        while l < n - 1:
            while r < n and nums[r] <= nums[l]:
                r += 1
            ans += n - r + (0 if r == l + 1 else 1)
            if nums[l + 1] > nums[l]:
                l += 1
            else:
                break
        return ans

Explain

这道题的解题思路主要是以移除子数组的左端点为基础进行枚举，并尝试找到每个可能的右端点。算法首先找到从数组末尾开始的第一个非递增的位置，这有助于快速排除那些不能作为子数组右端点的位置。之后，算法从数组开始处逐个尝试作为子数组的左端点，并寻找可能的右端点，从而确保移除后的数组是递增的。如果左端点和右端点之间的元素是递增的，则继续移动左端点。如果不是，则终止循环。对于每一个左端点和对应的右端点范围，计算可以形成的移除递增子数组数量，并累加到总数中。

时间复杂度: O(n)

空间复杂度: O(1)

# 定义类 Solution
class Solution:
    def incremovableSubarrayCount(self, nums: List[int]) -> int:
        n = len(nums) # 数组的长度
        r = n - 1 # 初始化右端点为数组的最后一个元素的位置
        ans = 0 # 初始化答案为0
        # 查找最左侧的非递增元素位置
        while r > 0 and nums[r - 1] < nums[r]:
            r -= 1
        # 如果找到非递增位置，计算初始的可移除递增子数组个数
        ans += n - r + (1 if r > 0 else 0)
        l = 0 # 初始化左端点为数组的第一个元素的位置
        # 遍历以每个元素为左端点的情况
        while l < n - 1:
            # 找到合适的右端点，确保移除后数组是递增的
            while r < n and nums[r] <= nums[l]:
                r += 1
            # 计算对应的子数组个数
            ans += n - r + (0 if r == l + 1 else 1)
            # 移动左端点到下一个可能的位置
            if nums[l + 1] > nums[l]:
                l += 1
            else:
                break # 如果不是递增的，停止处理
        return ans # 返回计算的结果

Explore

这个表达式用于计算从数组的右端开始，第一个非递增元素之后的所有元素可以单独作为递增子数组被移除的数量。这里`n - r`表示从第一个非递增位置到数组末尾的元素数量，每个都可以作为一个单独的子数组。如果`r > 0`，即存在至少一个递增的前缀，则整个数组也可以被视为一个可移除的递增子数组，因此需要加1。如果`r`为0，表明整个数组是递增的，不需要额外添加，因为整个数组本身就是一个子数组。

如果数组中所有元素都是递增的，那么初始化的`r`将会是0，因为循环条件不成立，`r`不会减少。这意味着整个数组本身是一个大的递增子数组。在这种情况下，算法会计算整个数组作为一个可移除的子数组，并且不会进一步拆分为更小的子数组。因此，算法的执行会正确处理这种极端情况，并返回正确的结果，即整个数组作为一个子数组。

这个计算方式用于统计从当前左端点`l`开始可能的递增子数组的数量。`n - r`是从当前右端点`r`到数组末尾的元素个数，每个都可以独立地作为递增子数组。条件`(0 if r == l + 1 else 1)`用于处理边界情况，当`r`恰好是`l + 1`时，表示在`l`和`r`之间没有足够的空间形成一个可移除的子数组，因此不会增加额外的子数组数量。如果`r`不等于`l + 1`，则至少有一个元素处于`l`和`r`之间，可以形成一个新的子数组，所以加1。