Easy

题目描述

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

如果 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]，因为移除其中任何一个子数组后，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 <= 50
  • 1 <= nums[i] <= 50

解题思路

这是一道枚举题，需要检查所有可能的子数组。

解题思路：

  1. 暴力枚举：由于数组长度最大为50，我们可以枚举所有可能的子数组 [i, j]，然后检查移除这个子数组后剩余部分是否严格递增。

  2. 检查严格递增：移除子数组 [i, j] 后，剩余部分为 nums[0...i-1] 和 nums[j+1...n-1]。需要检查：

    • nums[0...i-1] 本身是否严格递增
    • nums[j+1...n-1] 本身是否严格递增
    • 如果两部分都存在，还要检查 nums[i-1] < nums[j+1]

  3. 优化思路：可以预处理出从左侧开始的最长严格递增前缀和从右侧开始的最长严格递增后缀，这样能更高效地判断。

算法流程：

  • 使用两层循环枚举所有子数组 [i, j]
  • 对于每个子数组，检查移除后剩余部分是否严格递增
  • 统计满足条件的子数组数量

由于数据规模较小，直接暴力枚举即可，时间复杂度 O(n³) 是可以接受的。

代码实现

class Solution {
public:
    int incremovableSubarrayCount(vector<int>& nums) {
        int n = nums.size();
        int count = 0;
        
        // 枚举所有可能的子数组 [i, j]
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isStrictlyIncreasing(nums, i, j)) {
                    count++;
                }
            }
        }
        
        return count;
    }
    
private:
    bool isStrictlyIncreasing(vector<int>& nums, int removeStart, int removeEnd) {
        int n = nums.size();
        int prev = -1;
        
        // 检查移除子数组前的部分
        for (int i = 0; i < removeStart; i++) {
            if (prev != -1 && nums[i] <= prev) {
                return false;
            }
            prev = nums[i];
        }
        
        // 检查移除子数组后的部分
        for (int i = removeEnd + 1; i < n; i++) {
            if (prev != -1 && nums[i] <= prev) {
                return false;
            }
            prev = nums[i];
        }
        
        return true;
    }
};

class Solution:
    def incremovableSubarrayCount(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        
        # 枚举所有可能的子数组 [i, j]
        for i in range(n):
            for j in range(i, n):
                if self.is_strictly_increasing(nums, i, j):
                    count += 1
        
        return count
    
    def is_strictly_increasing(self, nums, remove_start, remove_end):
        n = len(nums)
        prev = -1
        
        # 检查移除子数组前的部分
        for i in range(remove_start):
            if prev != -1 and nums[i] <= prev:
                return False
            prev = nums[i]
        
        # 检查移除子数组后的部分
        for i in range(remove_end + 1, n):
            if prev != -1 and nums[i] <= prev:
                return False
            prev = nums[i]
        
        return True

public class Solution {
    public int IncremovableSubarrayCount(int[] nums) {
        int n = nums.Length;
        int count = 0;
        
        // 枚举所有可能的子数组 [i, j]
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (IsStrictlyIncreasing(nums, i, j)) {
                    count++;
                }
            }
        }
        
        return count;
    }
    
    private bool IsStrictlyIncreasing(int[] nums, int removeStart, int removeEnd) {
        int n = nums.Length;
        int prev = -1;
        
        // 检查移除子数组前的部分
        for (int i = 0; i < removeStart; i++) {
            if (prev != -1 && nums[i] <= prev) {
                return false;
            }
            prev = nums[i];
        }
        
        // 检查移除子数组后的部分
        for (int i = removeEnd + 1; i < n; i++) {
            if (prev != -1 && nums[i] <= prev) {
                return false;
            }
            prev = nums[i];
        }
        
        return true;
    }
}

var incremovableSubarrayCount = function(nums) {
    const n = nums.length;
    let count = 0;
    
    // 枚举所有可能的子数组 [i, j]
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            if (isStrictlyIncreasing(nums, i, j)) {
                count++;
            }
        }
    }
    
    return count;
    
    function isStrictlyIncreasing(nums, removeStart, removeEnd) {
        const n = nums.length;
        let prev = -1;
        
        // 检查移除子数组前的部分
        for (let i = 0; i < removeStart; i++) {
            if (prev !== -1 && nums[i] <= prev) {
                return false;
            }
            prev = nums[i];
        }
        
        // 检查移除子数组后的部分
        for (let i = removeEnd + 1; i < n; i++) {
            if (prev !== -1 && nums[i] <= prev) {
                return false;
            }
            prev = nums[i];
        }
        
        return true;
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n³) - 两层循环枚举所有子数组 O(n²)，每次检查严格递增性 O(n)
空间复杂度O(1) - 只使用了常数额外空间

相关题目