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;
        }
        
        // Find the longest increasing suffix
        int right = n - 1;
        while (right > 0 && nums[right - 1] < nums[right]) {
            right--;
        }
        
        long long result = 0;
        
        // Count subarrays that remove everything after prefix
        result += left + 2; // prefix lengths 0, 1, ..., left+1
        
        // For each suffix position, count valid prefixes
        for (int j = right; j < n; j++) {
            // Binary search or two pointers to find valid prefixes
            int validPrefixLen = 0;
            for (int i = 0; i <= left; i++) {
                if (nums[i] < nums[j]) {
                    validPrefixLen = i + 1;
                } else {
                    break;
                }
            }
            result += validPrefixLen;
        }
        
        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
        
        # Find the longest increasing suffix
        right = n - 1
        while right > 0 and nums[right - 1] < nums[right]:
            right -= 1
        
        result = 0
        
        # Count subarrays that remove everything after prefix
        result += left + 2  # prefix lengths 0, 1, ..., left+1
        
        # For each suffix position, use two pointers
        i = 0
        for j in range(right, n):
            # Find the largest prefix that can be combined with suffix starting at j
            while i <= left and nums[i] >= nums[j]:
                i += 1
            result += i
        
        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;
        }
        
        // Find the longest increasing suffix
        int right = n - 1;
        while (right > 0 && nums[right - 1] < nums[right]) {
            right--;
        }
        
        long result = 0;
        
        // Count subarrays that remove everything after prefix
        result += left + 2; // prefix lengths 0, 1, ..., left+1
        
        // For each suffix position, use two pointers
        int i = 0;
        for (int j = right; j < n; j++) {
            // Find the largest prefix that can be combined with suffix starting at j
            while (i <= left && nums[i] >= nums[j]) {
                i++;
            }
            result += i;
        }
        
        return result;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var incremovableSubarrayCount = function(nums) {
    const n = nums.length;
    
    // Find the longest strictly increasing prefix
    let prefix = 0;
    while (prefix < n - 1 && nums[prefix] < nums[prefix + 1]) {
        prefix++;
    }
    
    // If the entire array is strictly increasing
    if (prefix === n - 1) {
        return (n * (n + 1)) / 2;
    }
    
    // Find the longest strictly increasing suffix
    let suffix = n - 1;
    while (suffix > 0 && nums[suffix - 1] < nums[suffix]) {
        suffix--;
    }
    
    let count = 0;
    
    // Count subarrays that start from index 0
    count += prefix + 2; // prefix + 1 subarrays + the entire array
    
    // Count subarrays that end at index n-1 (excluding the entire array)
    count += n - suffix;
    
    // Count subarrays that keep both prefix and suffix
    let j = suffix;
    for (let i = 0; i <= prefix; i++) {
        // Find the first element in suffix that is greater than nums[i]
        while (j < n && nums[j] <= nums[i]) {
            j++;
        }
        count += n - j;
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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

时间复杂度分析：

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

空间复杂度分析：

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

相关题目