Hard

题目描述

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

如果移除 nums 的某个子数组后，nums 变成严格递增的数组，则这个子数组称为可移除子数组。例如，[3, 4] 是数组 [5, 3, 4, 6, 7] 的一个可移除子数组，因为移除这个子数组后，数组 [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]，因为移除任何一个子数组后，nums 都会变成严格递增的。注意不能选择空子数组。

示例 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^5
  • 1 <= nums[i] <= 10^9

解题思路

这是一个双指针优化问题。核心思想是找出数组的递增前缀和递增后缀，然后计算它们的有效组合数。

分析思路：

  1. 找到最大的递增前缀：从左到右找到最长的严格递增序列，记录下标为 left
  2. 找到最小的递增后缀：从右到左找到最长的严格递增序列，记录下标为 right
  3. 对于每个保留的前缀 nums[0...i]，需要找到能与之拼接的后缀 nums[j...n-1]，使得 nums[i] < nums[j]

关键观察：

  • 如果整个数组都是递增的，那么可以移除任何子数组，总数为 n*(n+1)/2
  • 否则，我们需要枚举保留的前缀长度，对于每个前缀，使用双指针找到合适的后缀起始位置
  • 当前缀长度增加时，后缀的起始位置单调不减，这是双指针优化的关键

算法步骤：

  1. 计算递增前缀的最大长度
  2. 计算递增后缀的最小起始位置
  3. 特殊处理：如果整个数组递增，直接返回 n*(n+1)/2
  4. 使用双指针枚举前缀和后缀的组合，统计可移除子数组数量

代码实现

class Solution {
public:
    long long incremovableSubarrayCount(vector<int>& nums) {
        int n = nums.size();
        
        // Find the longest increasing prefix
        int left = 0;
        while (left < n - 1 && nums[left] < nums[left + 1]) {
            left++;
        }
        
        // If the whole array is increasing
        if (left == n - 1) {
            return (long long)n * (n + 1) / 2;
        }
        
        long long result = left + 2;

        // Extend an increasing suffix from right to left. For each suffix,
        // keep only prefixes whose final value is smaller than its first value.
        for (int right = n - 1; right > 0; right--) {
            while (left >= 0 && nums[left] >= nums[right]) {
                left--;
            }
            result += left + 2;

            if (nums[right - 1] >= nums[right]) {
                break;
            }
        }
        
        return result;
    }
};

class Solution:
    def incremovableSubarrayCount(self, nums: List[int]) -> int:
        n = len(nums)
        
        # Find the longest increasing prefix
        left = 0
        while left < n - 1 and nums[left] < nums[left + 1]:
            left += 1
        
        # If the whole array is increasing
        if left == n - 1:
            return n * (n + 1) // 2
        
        result = left + 2

        # 从右向左扩展递增后缀，并收缩无法与后缀拼接的前缀
        for right in range(n - 1, 0, -1):
            while left >= 0 and nums[left] >= nums[right]:
                left -= 1
            result += left + 2

            if nums[right - 1] >= nums[right]:
                break
        
        return result

public class Solution {
    public long IncremovableSubarrayCount(int[] nums) {
        int n = nums.Length;
        
        // Find the longest increasing prefix
        int left = 0;
        while (left < n - 1 && nums[left] < nums[left + 1]) {
            left++;
        }
        
        // If the whole array is increasing
        if (left == n - 1) {
            return (long)n * (n + 1) / 2;
        }
        
        long result = left + 2;

        // Extend an increasing suffix and shrink incompatible prefixes.
        for (int right = n - 1; right > 0; right--) {
            while (left >= 0 && nums[left] >= nums[right]) {
                left--;
            }
            result += left + 2;

            if (nums[right - 1] >= nums[right]) {
                break;
            }
        }
        
        return result;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var incremovableSubarrayCount = function(nums) {
    const n = nums.length;

    let left = 0;
    while (left < n - 1 && nums[left] < nums[left + 1]) {
        left++;
    }

    if (left === n - 1) {
        return (n * (n + 1)) / 2;
    }

    let result = left + 2;

    for (let right = n - 1; right > 0; right--) {
        while (left >= 0 && nums[left] >= nums[right]) {
            left--;
        }
        result += left + 2;

        if (nums[right - 1] >= nums[right]) {
            break;
        }
    }

    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

项目复杂度
时间复杂度O(n)
空间复杂度O(1)

时间复杂度分析：

  • 找递增前缀：O(n)
  • 找递增后缀：O(n)
  • 双指针遍历：O(n)，因为每个指针最多移动n次
  • 总时间复杂度：O(n)

空间复杂度分析：

  • 只使用了常数个变量存储指针位置和计数结果
  • 空间复杂度：O(1)

相关题目