应用运算使所有数组元素等于零

Question

所以我尝试了这个leetcode问题，并且我能够想出一个通过1017/1026个测试用例的解决方案。其余失败的原因是超过时间限制，而不是解决方案不正确。所以我想知道是否有人对如何优化我的方法有任何想法。我知道这与我每次都在子列表中找到最小值有关。我很确定这可以通过一些前缀和逻辑来优化，但我不确定如何将其引入我的方法中。

问题来了：

给定一个 0 索引的整数数组 nums 和一个正整数 k。

您可以对任意数量的数组应用以下操作 次数：

从数组中选择任意大小为 k 的子数组，并减少其所有 元素除 1。如果可以使所有数组元素都成立，则返回 true 等于 0，否则为 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。

这是我的代码：

def checkArray(self, nums: List[int], k: int) -> bool:
        i, j = 0, k        
        while i + k <= len(nums):            
            sublist = nums[i:j]  # Make a copy of the sublist            
            smallest = min(sublist)
            for x in range(len(sublist)):                
                sublist[x] -= smallest  # Modify the values in the sublist
                if x > 0 and sublist[x] < sublist[x-1]:
                    return False
            nums[i:j] = sublist  # Assign the modified sublist back to the original list            
            i += 1
            j += 1
        return sum(nums) == 0

这是我的直觉，因此可以遵循我的方法：

我所做的是使用滑动窗口。在每个窗口内，我们正在做 两件事，我们正在模拟应用操作来减少 元素设置为 0，我们还通过检查窗口是否处于优化状态 有效的。如果当前窗口左侧没有元素，则窗口有效 模拟完成后，对元素进行迭代会更大。它 这是有道理的，因为如果左边的元素比它大，那么 表示窗口内左边的元素不能减为0 尺寸为 k。我所说的模拟只是指而不是连续地 将窗口中所有元素减1，直到最小 达到 0 时，我们只需找到窗口中最小的元素即可 从窗口中的所有元素中减去它。它产生相同的结果 但效率更高。

Answer 1

我们可以采用以下贪心方法：每当向前迭代时遇到非零元素时，我们就从该元素开始减少整个大小范围

k

，减去该元素的值。不需要寻找范围内的最小值，就好像范围内有任何一个值小于左端点的值，不可能让所有元素都等于0。为了快速进行范围更新，我们可以利用差异数组。

示例实现：

class Solution:
    def checkArray(self, nums: List[int], k: int) -> bool:
        diff = [0] * (len(nums) + 1)
        for i, v in enumerate(nums):
            if i: diff[i] += diff[i - 1]
            v += diff[i]
            if v < 0: return False
            if v:
                if i + k > len(nums): return False
                diff[i] -= v
                diff[i + k] += v
        return True