Medium

题目描述

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

你可以对数组执行下述操作 任意次：

  • 从数组中选择长度为 k 的 任一 子数组，将其所有元素都减去 1。

如果你可以使数组中的所有元素都等于 0，返回 true；否则，返回 false。

子数组 是数组中一个非空的连续元素序列。

示例 1：

输入：nums = [2,2,3,1,1,0], k = 3
输出：true
解释：我们可以执行下述操作：
- 选择子数组 [2,2,3]。执行操作后，数组变为 nums = [1,1,2,1,1,0]。
- 选择子数组 [2,1,1]。执行操作后，数组变为 nums = [1,1,1,0,0,0]。
- 选择子数组 [1,1,1]。执行操作后，数组变为 nums = [0,0,0,0,0,0]。

示例 2：

输入：nums = [1,3,1,1], k = 2
输出：false
解释：无法使所有数组元素都等于 0。

提示：

  • 1 <= k <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^6

解题思路

这道题的关键思路是贪心策略：我们必须从左到右处理数组，对于每个位置，如果它的值大于0，我们就必须对以它为起点的长度为k的子数组进行操作。

核心观察：

  1. 如果某个位置的值需要减为0，那么包含这个位置的所有操作都必须在处理到这个位置之前完成
  2. 为了最大化效率，我们应该尽可能晚地进行操作，这样可以同时影响更多后续位置

算法思路：

  • 使用差分数组的思想，维护一个操作计数器
  • 从左到右遍历数组，对于位置i：
    • 首先应用之前操作对当前位置的影响
    • 如果当前值仍然大于0，说明需要以位置i为起点进行操作
    • 检查是否有足够的空间（i+k-1 < n）来执行长度为k的操作
    • 记录操作的结束位置，以便后续更新影响范围

时间复杂度优化：使用差分数组避免每次操作都要更新k个元素，而是只记录操作的开始和结束位置。

这种方法保证了我们能够在O(n)时间内判断是否可能将所有元素变为0。

代码实现

class Solution {
public:
    bool checkArray(vector<int>& nums, int k) {
        int n = nums.size();
        int operations = 0;  // 当前累积的操作次数
        
        for (int i = 0; i < n; i++) {
            // 如果超出了某个操作的影响范围，减少操作计数
            if (i >= k && nums[i - k] > 0) {
                operations -= nums[i - k];
            }
            
            // 计算当前位置经过操作后的实际值
            int currentVal = nums[i] - operations;
            
            if (currentVal < 0) {
                return false;  // 操作过多，值变为负数
            }
            
            if (currentVal > 0) {
                // 需要进行额外操作
                if (i + k > n) {
                    return false;  // 没有足够空间进行k长度的操作
                }
                operations += currentVal;
                nums[i] = currentVal;  // 记录在位置i开始的操作次数
            } else {
                nums[i] = 0;
            }
        }
        
        return true;
    }
};

class Solution:
    def checkArray(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        operations = 0  # 当前累积的操作次数
        
        for i in range(n):
            # 如果超出了某个操作的影响范围，减少操作计数
            if i >= k and nums[i - k] > 0:
                operations -= nums[i - k]
            
            # 计算当前位置经过操作后的实际值
            current_val = nums[i] - operations
            
            if current_val < 0:
                return False  # 操作过多，值变为负数
            
            if current_val > 0:
                # 需要进行额外操作
                if i + k > n:
                    return False  # 没有足够空间进行k长度的操作
                operations += current_val
                nums[i] = current_val  # 记录在位置i开始的操作次数
            else:
                nums[i] = 0
        
        return True

public class Solution {
    public bool CheckArray(int[] nums, int k) {
        int n = nums.Length;
        int operations = 0;  // 当前累积的操作次数
        
        for (int i = 0; i < n; i++) {
            // 如果超出了某个操作的影响范围，减少操作计数
            if (i >= k && nums[i - k] > 0) {
                operations -= nums[i - k];
            }
            
            // 计算当前位置经过操作后的实际值
            int currentVal = nums[i] - operations;
            
            if (currentVal < 0) {
                return false;  // 操作过多，值变为负数
            }
            
            if (currentVal > 0) {
                // 需要进行额外操作
                if (i + k > n) {
                    return false;  // 没有足够空间进行k长度的操作
                }
                operations += currentVal;
                nums[i] = currentVal;  // 记录在位置i开始的操作次数
            } else {
                nums[i] = 0;
            }
        }
        
        return true;
    }
}

var checkArray = function(nums, k) {
    const n = nums.length;
    let operations = 0;  // 当前累积的操作次数
    
    for (let i = 0; i < n; i++) {
        // 如果超出了某个操作的影响范围，减少操作计数
        if (i >= k && nums[i - k] > 0) {
            operations -= nums[i - k];
        }
        
        // 计算当前位置经过操作后的实际值
        const currentVal = nums[i] - operations;
        
        if (currentVal < 0) {
            return false;  // 操作过多，值变为负数
        }
        
        if (currentVal > 0) {
            // 需要进行额外操作
            if (i + k > n) {
                return false;  // 没有足够空间进行k长度的操作
            }
            operations += currentVal;
            nums[i] = currentVal;  // 记录在位置i开始的操作次数
        } else {
            nums[i] = 0;
        }
    }
    
    return true;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)只需要遍历数组一次，每个元素处理时间为常数
空间复杂度O(1)只使用了常数额外空间，原地修改数组

相关题目