使数组中的所有元素都等于零
难度:
标签:
题目描述
You are given a 0-indexed integer array nums
and a positive integer k
.
You can apply the following operation on the array any number of times:
- Choose any subarray of size
k
from the array and decrease all its elements by1
.
Return true
if you can make all the array elements equal to 0
, or false
otherwise.
A subarray is a contiguous non-empty part of an array.
Example 1:
Input: nums = [2,2,3,1,1,0], k = 3 Output: true Explanation: We can do the following operations: - Choose the subarray [2,2,3]. The resulting array will be nums = [1,1,2,1,1,0]. - Choose the subarray [2,1,1]. The resulting array will be nums = [1,1,1,0,0,0]. - Choose the subarray [1,1,1]. The resulting array will be nums = [0,0,0,0,0,0].
Example 2:
Input: nums = [1,3,1,1], k = 2 Output: false Explanation: It is not possible to make all the array elements equal to 0.
Constraints:
1 <= k <= nums.length <= 105
0 <= nums[i] <= 106
代码结果
运行时间: 62 ms, 内存: 28.8 MB
/*
* Problem: Given an integer array 'nums' and a positive integer 'k',
* determine if it is possible to make all elements of the array equal to 0
* by repeatedly selecting any subarray of length 'k' and subtracting 1 from each element of that subarray.
*
* Approach (using Java Streams):
* 1. Iterate through the array and reduce the first 'k' elements by the minimum value among them.
* 2. Repeat the process for subsequent elements until the whole array is checked.
* 3. If at any point, the remaining elements can't form a subarray of length 'k', return false.
* 4. If all elements are reduced to zero, return true.
*/
import java.util.Arrays;
import java.util.stream.IntStream;
public class SolutionStream {
public boolean canMakeAllZero(int[] nums, int k) {
int n = nums.length;
int[] sub = new int[n + 1];
IntStream.range(0, n).forEach(i -> {
if (i >= k) sub[i] += sub[i - k];
nums[i] -= sub[i];
if (nums[i] < 0) throw new IllegalStateException("Can't make all elements zero");
if (nums[i] > 0) sub[i] += nums[i];
});
return IntStream.of(nums).allMatch(x -> x == 0);
}
}
解释
方法:
题解的思路基于差分数组的概念。差分数组允许我们对数组的子区间进行增减操作。在本题中,我们的目标是通过减少操作使得数组中的所有元素变为0。首先创建一个差分数组dis,初始全为0。遍历原数组,利用差分数组来更新当前元素实际值,并判断当前元素是否需要进一步操作。如果当前元素值已经为0,则不需要操作;如果当前元素值小于0或者无法形成长度为k的子区间,则返回false。否则,根据当前元素值调整差分数组,以反映对后续元素的影响。最终,如果能够遍历完整个数组而不返回false,则说明可以通过操作使所有元素变为0。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在题解中使用差分数组而不是直接修改原数组?
▷🦆
差分数组的dis[i + k] += x操作是如何确保不会对数组dis越界访问?
▷🦆
在判断x < 0时,为什么直接返回false,数组中的负数值是否有可能在后续操作中被调整为0?
▷🦆
题解中提到`如果当前元素值小于0或者无法形成长度为k的子区间,则返回false`,但如果当前元素为负,是否存在某种方式通过增加操作使其变为0?
▷