leetcode
leetcode 2351 ~ 2400
使数组中的所有元素都等于零

使数组中的所有元素都等于零

难度:

标签:

题目描述

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 by 1.

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)

代码细节讲解

🦆
为什么在题解中使用差分数组而不是直接修改原数组?
使用差分数组的主要原因是它允许我们高效地进行区间修改。在处理需要频繁对数组的子区间增减的问题时,直接修改原数组会导致重复计算和较高的时间复杂度,尤其是在大数组和多次修改的情况下。差分数组通过记录每个区间的变化量,使得更新操作的时间复杂度从O(n)降低到O(1),整体上提高了算法的效率。
🦆
差分数组的dis[i + k] += x操作是如何确保不会对数组dis越界访问?
在本题解中,确保不越界的关键在于算法逻辑中的条件检查`if i + k > n`。这个条件保证了在执行`dis[i + k] += x`操作时,索引`i + k`总是有效的,即不会超过数组`dis`的最大索引。这是因为数组`dis`的长度被定义为`n + 1`,因此即使在最大的有效索引`i + k`上进行操作,也不会越界。
🦆
在判断x < 0时,为什么直接返回false,数组中的负数值是否有可能在后续操作中被调整为0?
在本题的逻辑中,如果在任何时刻元素`x`的值小于0,则意味着无法通过减少操作使其达到0,因为差分数组只能用于执行增减操作而不能改变操作的方向(只能做减法不能变为做加法)。因此,如果`x`已经小于0,则没有后续操作能将其增加到0,这导致无法满足题目要求使所有元素等于0,所以直接返回false是合理的。
🦆
题解中提到`如果当前元素值小于0或者无法形成长度为k的子区间,则返回false`,但如果当前元素为负,是否存在某种方式通过增加操作使其变为0?
在本题的框架和定义下,不存在这样的操作。差分数组的设计是基于增减相同的值于连续子区间,且这里的操作被设定为只能减少。如果元素值已经是负数,我们没有办法通过差分数组的减少操作来增加它的值。此外,题述中也没有提供其他机制或操作来允许从负数调整到0,因此在当前元素值小于0时返回false是符合题目逻辑的。

相关问题