题目描述
给你一个下标从 0 开始的整数数组 nums
和一个正整数 k
。
你可以对数组执行下述操作 任意次:
- 从数组中选出长度为
k
的 任一 子数组,并将子数组中每个元素都 减去1
。
如果你可以使数组中的所有元素都等于 0
,返回 true
;否则,返回 false
。
子数组 是数组中的一个非空连续元素序列。
样例
输入: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]。
输入:nums = [1,3,1,1], k = 2
输出:false
解释:无法使数组中的所有元素等于 0。
限制
1 <= k <= nums.length <= 10^5
0 <= nums[i] <= 10^6
算法
(思维题) $O(n)$
- 从前往后依次遍历数组,保证遍历过之后的位置都可以变为 $0$,如果无法做到则中途返回 $false$。
- 定义 $sum$,表示到当前位置时,由于前面不为 $0$ 时,当前位置被动需要减去的总和。
- 首先遍历 $[0, n - k]$,如果 $i \ge k$,则说明 $i - k$ 位置的影响已经消除,则 $sum = sum - nums(i - k)$。接下来如果 $nums(i) < sum$,则说明不合法,返回 $false$。令 $nums(i) = nums(i) - sum$,$nums(i)$ 余下的值就是本次在 $i$ 位置需要做的减法次数,则 $sum = sum + nums(i)$。
- 最后遍历 $[n - k + 1, n - 1]$,同样如果 $i \ge k$,则 $sum = sum - nums(i - k)$,如果 $nums(i) \neq sum$,则无法做到清 $0$,因为这些位置不能再做额外的减法操作了。
时间复杂度
- 遍历数组一次,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
bool checkArray(vector<int>& nums, int k) {
const int n = nums.size();
int sum = 0;
for (int i = 0; i < n - k + 1; i++) {
if (i >= k)
sum -= nums[i - k];
if (nums[i] < sum)
return false;
nums[i] -= sum;
sum += nums[i];
}
for (int i = n - k + 1; i < n; i++) {
if (i >= k)
sum -= nums[i - k];
if (nums[i] != sum)
return false;
}
return true;
}
};