[LeetCode] 每日一题 3355. 零数组变换 I（差分数组）

题目描述

给定一个长度为 n 的整数数组 nums 和一个二维数组 queries，其中 queries[i] = [li, ri]。

对于每个查询 queries[i]：

• 在 nums 的下标范围 [li, ri] 内选择一个下标 子集。

• 将选中的每个下标对应的元素值减 1。

零数组 是指所有元素都等于 0 的数组。

如果在按顺序处理所有查询后，可以将 nums 转换为 零数组 ，则返回 true，否则返回 false。

题目链接

https://leetcode.cn/problems/zero-array-transformation-i

示例输入

示例 1

输入： nums = [1,0,1], queries = [[0,2]]

输出： true

解释：

对于 i = 0：
选择下标子集 [0, 2] 并将这些下标处的值减 1。
数组将变为 [0, 0, 0]，这是一个零数组。

示例 2

输入： nums = [4,3,2,1], queries = [[1,3],[0,2]]

输出： false

解释：

对于 i = 0： 
选择下标子集 [1, 2, 3] 并将这些下标处的值减 1。
数组将变为 [4, 2, 1, 0]。
对于 i = 1：
选择下标子集 [0, 1, 2] 并将这些下标处的值减 1。
数组将变为 [3, 1, 0, 0]，这不是一个零数组。

提示

• 1 <= nums.length <= 10^5

• 0 <= nums[i] <= 10^5

• 1 <= queries.length <= 10^5

• queries[i].length == 2

• 0 <= li <= ri < nums.length

解题思路

今天这题看起来挺有意思的，虽然题目要求我们对特定范围内的元素执行减1操作，但本质上其实是“批量修改 + 范围限制”的问题。一开始我也和很多人一样，第一反应是模拟，或者用 HashMap 来尝试标记每个区间，但写起来不仅麻烦，而且效率也不高。

后来我突然想到，既然我们对的是连续范围操作，其实“前缀和”不就是一种能高效表示区间影响的结构吗？进一步一想，我们不是要统计和，而是要批量减1，这其实就是“差分数组”的经典应用场景。

所以我就用了一个差分数组 pre[]，在每个区间的 left 位置标记 -1，在 right + 1 的地方加 1，表示这个区间整体减去 1，遍历时通过前缀和计算当前位置最终被减了多少，最终判断每个位置的值是否都能小于等于0。

代码逻辑非常简洁，效率也很高，520 这天能刷到一道关于“差分”的题目，这就是单身狗程序员的心声发泄吧😭😭

代码实现

class Solution {
    public boolean isZeroArray(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] pre = new int[n + 1];
        for (int[] query : queries) {
            pre[query[0]]--;
            pre[query[1] + 1]++;
        }
        int prefixSum = 0;
        for (int i = 0; i < n; i++) {
            prefixSum += pre[i];
            if (nums[i] + prefixSum > 0) {
                return false;
            }
        }
        return true;
    }
}

复杂度分析

• 时间复杂度🕒：

  • O(n + q) ，遍历所有区间是 O(q)，遍历数组进行前缀和计算是 O(n)。

• 空间复杂度📦：

  • O(n) ，使用了一个差分辅助数组 pre[]。

总结

本题是一个典型的“范围操作优化”问题，差分数组是这种问题中最常用的套路之一。它的精髓就在于：把“对一段区间进行加减”转化为“对两个点进行操作”，从而提升整体效率。值得一提的是，这个技巧在很多竞赛题中也非常常见，是打基础阶段必须掌握的一个技巧 👊

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。