【唐叔学算法】第七天：差分算法-高效处理数组区间更新的利器

本文链接：https://blog.csdn.net/Tang_is_learning/article/details/144334525

你是否曾为如何高效地修改数组中某个区间内所有元素的值而苦恼？差分算法，就像一把神奇的魔法棒，能帮你轻松实现区间修改。今天，就让我们一起揭开差分算法的神秘面纱，探索它在Java编程中的应用。

什么是差分？

定义

差分（Difference）可以看作是前缀和的逆运算。给定一个数组 a，其对应的差分数组 b 满足：

b[0] = a[0]
b[i] = a[i] - a[i-1] 对于 i > 0

例如，对于原数组 [1, 2, 3, 4]，差分数组为 [1, 1, 1, 1]。

而原数组 a 可以通过差分数组 b 的前缀和来恢复。即：

a[i] = b[0] + b[1] + ... + b[i]

基本原理

差分的主要用途在于当我们需要对数组中的某个区间 [l, r] 内的所有元素加上或减去一个相同的值 c 时，我们可以只对差分数组进行两次操作：

b[l] += c，表示从位置 l 开始的元素都增加 c。
b[r+1] -= c（如果 r+1 存在），表示从位置 r+1 开始的元素减少 c，从而抵消了对后续元素的影响。

应用场景

差分算法常用于以下场景：

区间更新：当需要对数组中的一段区间内的所有元素执行相同的加减操作时。
区间统计：如统计数组中某个区间内满足某种条件的元素个数。
前缀和或后缀和
差值问题
优化时间复杂度：通过差分数组，我们可以将多次区间操作的时间复杂度降低到 O(n)。

如何使用差分？

实现步骤

使用差分解决问题的一般步骤如下：

初始化差分数组：创建一个与原数组长度相同的差分数组，并根据原数组计算初始的差分值。
执行区间更新：对于每个区间更新操作，调整差分数组中的相应位置。
还原原始数组：通过对差分数组求前缀和，得到最终的更新后的数组。

注意事项

差分数组的长度：差分数组的长度比原数组多 1。
区间修改的处理：需要正确处理区间起始位置和结束位置的偏移。
空间复杂度：虽然差分数组提供了时间效率上的优势，但也会占用额外的空间，因此在内存有限的情况下需要注意。

LeetCode实战解析

入门题：1109. 航班预订统计

题目链接：1109. 航班预订统计

题目描述：有 n 个航班，按顺序编号为 1 到 n。我们有 k 个预定记录，每个记录包含两个整数 i 和 j，表示第 i 个航班到第 j 个航班之间（包括两端）的座位被预订了一次。请返回一个长度为 n 的数组，其中答案 [k] 表示第 k 个航班上预订的座位总数。

解题思路

这个问题可以通过差分数组来解决。我们创建一个大小为 n+1 的差分数组 diff，然后遍历每个预订记录，对差分数组的相应位置进行更新。最后，通过前缀和的方式计算出每个航班的预订座位数。

Java代码实现

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] diff = new int[n + 1];
        for (int[] booking : bookings) {
            int start = booking[0], end = booking[1], seats = booking[2];
            diff[start - 1] += seats;
            if (end < n) {
                diff[end] -= seats;
            }
        }

        // 计算前缀和
        int[] result = new int[n];
        result[0] = diff[0];
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] + diff[i];
        }

        return result;
    }
}

中等题：1456. 定长子串中元音的最大数目

题目链接：1456. 定长子串中元音的最大数目

题目描述：给你一个字符串 s 和一个整数 k，请你返回 s 中长度为 k 的子串中元音字母的最大数量。

解题思路

此题可以通过滑动窗口结合差分思想来解决。首先，我们需要定义一个辅助函数来判断字符是否为元音。接着，我们利用一个计数器来跟踪当前窗口内元音的数量，并通过滑动窗口来更新最大值。

Java代码实现

class Solution {
    public int maxVowels(String s, int k) {
        int maxCount = 0, currentCount = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (isVowel(c)) {
                currentCount++;
            }
            if (i >= k && isVowel(s.charAt(i - k))) {
                currentCount--;
            }
            maxCount = Math.max(maxCount, currentCount);
        }
        return maxCount;
    }

    private boolean isVowel(char c) {
        return "aeiou".indexOf(c) != -1;
    }
}

结语

差分算法作为一种高效的算法技巧，能够显著提升区间增减值问题的解决效率。通过本文的学习，相信大家对差分算法有了更深入的理解。在实际应用中，差分算法虽然强大，但也需要注意边界条件的设定和操作的准确性。希望各位读者朋友能够在实践中灵活运用差分算法，解决更多的编程问题。如果有任何疑问或建议，欢迎在评论区留言交流！让我们一起享受编程的乐趣，不断探索和学习！

如果喜欢这篇文章，别忘了点赞和分享哦！我是唐叔，我们下次再见！