当前位置：首页 > news >正文

算法：定义一个数组的的陡峭值为:相邻两个元素之差的绝对值之和。

news 来源：原创 2025/9/3 4:01:56

定义一个数组的的陡峭值为:相邻两个元素之差的绝对值之和。现在小红拿到了一个数组，她有多次询问，每次查询一段连续子数组的陡峭值。你能帮帮她吗?
连续子数组为从原数组中，连续的选择一段元素(可以全选、可以不选)得到的新数组。
输入描述
第一行输入一个正整数n，代表数组长度。
第二行输入n个正整数ai，代表小红拿到的数组。
第三行输入一个正整数q，代表询问次数。
接下来的q行，每行输入两个正整数l,r代表一次询问.
1 ≤ n,q≤ 10^5,1 ≤ ai ≤ 10^9
1≤l≤r≤n
输出描述
输出q行，每行输出一个正整数，代表查询的结果
以上是一道算法题，请使用java代码实现，标准输入输出

以下是使用 Scanner 输入的 Java 代码实现：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = scanner.nextInt();}// 计算差值数组dint[] d = new int[n - 1];for (int i = 0; i < n - 1; i++) {d[i] = Math.abs(a[i + 1] - a[i]);}// 计算前缀和数组sumint[] sum = new int[n];for (int i = 1; i < n; i++) {sum[i] = sum[i - 1] + d[i - 1];}// 处理查询int q = scanner.nextInt();for (int i = 0; i < q; i++) {int l = scanner.nextInt();int r = scanner.nextInt();if (l == r) {System.out.println(0);} else {// 转换为0-based索引System.out.println(sum[r - 1] - sum[l - 1]);}}scanner.close();}
}

修改说明：

输入方式替换：
将 BufferedReader 替换为 Scanner，通过 scanner.nextInt() 直接读取整数。
数组读取：
使用循环逐个读取数组元素，避免 split 的字符串处理。
查询处理：
直接通过 scanner.nextInt() 读取 l 和 r，无需额外处理字符串分割。

代码逻辑保持不变：

预处理差值数组：计算相邻元素的绝对差值。
前缀和数组：通过前缀和快速计算任意区间的陡峭值。
查询优化：每个查询的时间复杂度为 O(1)，总时间复杂度为 O(n + q)。

输入输出示例：

输入：

输出：

2
4

解释：

区间 [1,2] 的差值为 |3-1|=2。
区间 [1,3] 的差值为 |3-1| + |5-3| = 2 + 2 = 4。

优化复杂度（建议将int全部换成long避免数据溢出）

以下是优化后的代码，通过减少数组的使用和避免溢出，同时保持内存效率：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = scanner.nextInt();}// 直接计算前缀和，省去差值数组dlong[] sum = new long[n]; // 使用long防止溢出for (int i = 1; i < n; i++) {sum[i] = sum[i - 1] + Math.abs(a[i] - a[i - 1]);}int q = scanner.nextInt();for (int i = 0; i < q; i++) {int l = scanner.nextInt();int r = scanner.nextInt();if (l == r) {System.out.println(0);} else {// 转换为0-based索引System.out.println(sum[r - 1] - sum[l - 1]);}}scanner.close();}
}

优化说明：

省去差值数组 d：
- 直接在计算前缀和数组 sum 时，边计算差值边累加，不再需要单独的 d 数组，节省了 O(n) 的空间。
使用 long 类型的前缀和数组：
- 原差值可能达到 2e9，当 n=1e5 时，总和可能超过 int 的范围（最大值为 2^31-1≈2e9），因此必须使用 long 类型以避免溢出。
内存优化效果：
- 原方案需要存储 d（int[n-1]）和 sum（int[n]），总空间为 4n（以字节计算）。
- 新方案仅用 long[n] 的 sum，空间为 8n，但通过省去 d 数组，总内存与原方案相近，同时避免了溢出问题。

复杂度分析：

时间复杂度：预处理为 O(n)，每个查询为 O(1)，总时间复杂度仍为 O(n + q)。
空间复杂度：O(n)，仅需存储原始数组 a 和前缀和数组 sum。

输入输出示例：

输入：

输出：

2
4

关键点总结：

避免溢出：差值总和可能超过 int 的范围，必须使用 long。
减少数组：直接计算前缀和，无需额外存储差值数组，节省内存。
高效查询：通过前缀和实现 O(1) 时间的区间查询。

修改说明：

代码逻辑保持不变：

输入输出示例：

优化复杂度（建议将int全部换成long避免数据溢出）

优化说明：

复杂度分析：

输入输出示例：

关键点总结：

相关文章：