零基础数据结构与算法——第六章：算法设计范式与高级主题-设计技巧(下)

6.1 算法设计技巧

设计技巧(上)

6.1.3 预处理与索引

基本概念

预处理是指在主要算法执行之前，对输入数据进行一些预先处理，以便简化后续的计算。索引是一种数据结构，用于加速数据查找操作。这就像在做一道复杂菜肴前，先把所有食材洗好、切好、分类好，这样在烹饪过程中就能更加高效。

预处理和索引的核心思想是：花费一次性的前期工作，换取后续多次操作的效率提升。

生活中的例子

图书馆的图书分类系统：

• 图书馆不会随机摆放书籍，而是按照分类系统（如杜威十进制分类法）组织图书
• 这种预处理需要初始投入（对所有书籍进行分类和编号）
• 但大大加快了后续查找特定书籍的速度
• 还有目录索引系统，可以通过作者、书名或主题快速找到书籍位置

厨房食材的准备工作：

• 专业厨师在烹饪前会做"mise en place"（法语，意为"放置到位"）
• 提前将所有食材洗净、切好、分类放好
• 虽然前期需要时间，但在实际烹饪过程中可以更加高效流畅

常见的预处理与索引技术

算法示例：前缀和与区间查询

假设我们有一个整数数组，需要频繁地计算数组中某个区间内所有元素的和。

方法1：直接计算（无预处理）

public static int rangeSum(int[] arr, int left, int right) {
int sum = 0;
for (int i = left; i <= right; i++) {
sum += arr[i];
}
return sum;
}

这种方法每次查询的时间复杂度为O(n)，其中n是区间长度。

方法2：使用前缀和（预处理）

// 构建前缀和数组
public static int[] buildPrefixSum(int[] arr) {
int n = arr.length;
int[] prefixSum = new int[n + 1]; // 注意大小为n+1

// prefixSum[i]表示arr[0]到arr[i-1]的和
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + arr[i];
}

return prefixSum;
}

// 使用前缀和计算区间和
public static int rangeSum(int[] prefixSum, int left, int right) {
// 区间[left, right]的和 = 前缀和[0, right] – 前缀和[0, left-1]
return prefixSum[right + 1] – prefixSum[left];
}

这种方法预处理时间复杂度为O(n)，但每次查询的时间复杂度降为O(1)。

图解前缀和

假设有数组：[3, 1, 4, 1, 5, 9, 2, 6]

前缀和数组：[0, 3, 4, 8, 9, 14, 23, 25, 31]

• prefixSum[0] = 0（空前缀）
• prefixSum[1] = 3（前1个元素和）
• prefixSum[2] = 4（前2个元素和）
• prefixSum[3] = 8（前3个元素和）
• …
• prefixSum[8] = 31（全部元素和）

计算区间和示例：

• 区间[2, 5]的和 = prefixSum[6] – prefixSum[2] = 23 – 4 = 19
• 区间[0, 7]的和 = prefixSum[8] – prefixSum[0] = 31 – 0 = 31
• 区间[4, 4]的和 = prefixSum[5] – prefixSum[4] = 14 – 9 = 5

二维前缀和

对于二维数组，也可以使用类似的技术：

// 构建二维前缀和
public static int[][] build2DPrefixSum(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) return new int[0][0];

int m = matrix.length;
int n = matrix[0].length;
int[][] prefixSum = new int[m + 1][n + 1];

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
prefixSum[i + 1][j + 1] = prefixSum[i + 1][j] + prefixSum[i][j + 1] –
prefixSum[i][j] + matrix[i][j];
}
}

return prefixSum;
}

// 计算子矩阵和
public static int subMatrixSum(int[][] prefixSum, int row1, int col1, int row2, int col2) {
return prefixSum[row2 + 1][col2 + 1] – prefixSum[row2 + 1][col1] –
prefixSum[row1][col2 + 1] + prefixSum[row1][col1];
}

应用场景

6.1.4 增量更新

基本概念

增量更新是一种只更新必要部分而不是重新计算整个结果的技术。这种方法在处理动态变化的数据时特别有用，可以大大提高算法的效率。就像修改文档时，我们只需要修改变动的部分，而不是重新打字整个文档。

增量更新的核心思想是：利用前一个状态的结果和新的变化，快速计算出新状态的结果。

生活中的例子

银行账户余额：

• 银行不会每次交易后重新计算你的所有历史交易
• 而是基于当前余额加上或减去新的交易金额
• 例如：余额1000元，消费200元，新余额 = 1000 – 200 = 800元

电子表格计算：

• 当你修改电子表格中的一个单元格时
• 只有依赖于该单元格的公式会被重新计算
• 其他无关的计算保持不变

社交媒体信息流：

• 当你打开社交媒体应用时，它不会重新加载所有内容
• 而是只加载自上次查看后的新内容
• 通常会显示"加载新内容"的选项

常见的增量更新技术

算法示例：滑动窗口最大值

假设我们有一个整数数组和一个大小为k的滑动窗口，窗口从数组的最左边滑动到最右边，我们需要找出窗口中的最大值。

方法1：暴力法（无增量更新）

public static int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n == 0 || k == 0) return new int[0];

int[] result = new int[n – k + 1];

for (int i = 0; i <= n – k; i++) {
int max = Integer.MIN_VALUE;
for (int j = i; j < i + k; j++) {
max = Math.max(max, nums[j]);
}
result[i] = max;
}

return result;
}

这种方法的时间复杂度为O(n*k)，因为对于每个窗口位置，我们都需要遍历k个元素找出最大值。

方法2：使用双端队列（增量更新）

public static int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n == 0 || k == 0) return new int[0];

int[] result = new int[n – k + 1];
// 使用双端队列存储可能成为窗口最大值的元素的索引
Deque<Integer> deque = new LinkedList<>();

for (int i = 0; i < n; i++) {
// 移除队列中所有小于当前元素的值（它们不可能是后续窗口的最大值）
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}

// 添加当前元素索引到队列
deque.offerLast(i);

// 移除队列中所有不在当前窗口范围内的元素
while (!deque.isEmpty() && deque.peekFirst() < i – k + 1) {
deque.pollFirst();
}

// 当窗口至少有k个元素时，记录当前窗口的最大值
if (i >= k – 1) {
result[i – k + 1] = nums[deque.peekFirst()];
}
}

return result;
}

这种方法的时间复杂度为O(n)，因为每个元素最多被处理两次（入队和出队）。

另一个例子：最大子数组和（Kadane算法）

最大子数组和问题是寻找一个数组中具有最大和的连续子数组。

public static int maxSubArraySum(int[] arr) {
// 如果数组为空，返回0
if (arr.length == 0) return 0;

int maxSoFar = arr[0]; // 记录全局最大子数组和
int maxEndingHere = arr[0]; // 记录以当前元素结尾的最大子数组和

for (int i = 1; i < arr.length; i++) {
// 增量更新：当前元素要么自己开始一个新的子数组，要么加入到前面的子数组
maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);

// 更新全局最大值
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}

return maxSoFar;
}

图解Kadane算法

假设数组为：[-2, 1, -3, 4, -1, 2, 1, -5, 4]

最终结果：最大子数组和为6，对应的子数组是[4, -1, 2, 1]。

应用场景