2025 A卷 200分 题型

本文涵盖详细的问题分析、解题思路、代码实现、代码详解、测试用例以及综合分析；
并提供Java、python、JavaScript、C++、C语言、GO六种语言的最佳实现方式！

2025华为OD真题目录+全流程解析/备考攻略/经验分享

华为OD机试真题《天然蓄水库》：

---

---

题目名称：天然蓄水库

---

• 知识点：双指针
• 时间限制：1秒
• 空间限制：256MB
• 限定语言：不限

---

题目描述

公元2919年，人类在X星山脉间建造天然蓄水库，需选取两边界使蓄水量最大。要求：

1. 山脉用数组s表示，元素为高度。
2. 边界内的蓄水量为两边界高度的最小值减去中间山脉占用的空间。
3. 若有多个解，选下标距离最近的边界。
4. 无法蓄水则输出0，否则输出左、右边界及蓄水量。

输入描述
一行正整数（空格分隔），如 1 9 6 2 5 4 9 3 7，表示s = [1,9,6,2,5,4,9,3,7]。

输出描述
若存在合理边界，输出格式为左边界 右边界:蓄水量，如1 6:19；否则输出0。

示例

示例1
输入：

1 9 6 2 5 4 9 3 7  

输出：

1 6:19  

说明：选s[1]（高9）和s[6]（高9），中间蓄水量为3+7+4+5=19。

示例2
输入：

3 2 1  

输出：

0  

补充说明

• 数组长度范围：1 <= length(s) <= 10000
• 山脉高度范围：0 <= s[i] <= 10000

---

Java

题目分析

题目要求在给定的山脉数组中选择两个边界，使得它们之间的蓄水量最大。蓄水量计算公式为：两边界高度的最小值 × 区间长度 - 中间山脉的总高度。需要处理以下关键点：

1. 高效计算：避免暴力枚举所有可能的左右边界（O(n²) 时间复杂度），采用双指针法实现 O(n) 时间复杂度。
2. 边界条件：处理无法蓄水的情况（结果 ≤ 0）和多个解时选择下标距离最近的边界。
3. 数据预处理：使用前缀和数组快速计算中间山脉的总高度。

---

解决思路

1. 双指针法：初始化左右指针分别指向数组首尾，每次移动较小高度的指针，保留较大高度的边界以探索更大蓄水量。
2. 前缀和优化：预处理前缀和数组，实现区间和 O(1) 查询。
3. 条件判断：维护最大蓄水量及对应的左右边界，处理距离更短的解。

---

Java 代码实现

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);String[] parts = scanner.nextLine().trim().split(" ");int n = parts.length;int[] s = new int[n];for (int i = 0; i < n; i++) {s[i] = Integer.parseInt(parts[i]);}if (n < 2) {System.out.println(0);return;}// 预处理前缀和数组，preSum[i] 表示前i个元素的总和int[] preSum = new int[n + 1];for (int i = 0; i < n; i++) {preSum[i + 1] = preSum[i] + s[i];}int left = 0, right = n - 1;int maxWater = 0;int bestLeft = -1, bestRight = -1;while (left < right) {int minH = Math.min(s[left], s[right]);int count = right - left - 1;if (count > 0) { // 仅当区间内有元素时计算int sumMiddle = preSum[right] - preSum[left + 1];int water = minH * count - sumMiddle;// 更新最大值或更优解（距离更近）if (water > maxWater) {maxWater = water;bestLeft = left;bestRight = right;} else if (water == maxWater) {int currentDistance = right - left;int bestDistance = bestRight - bestLeft;if (currentDistance < bestDistance || bestDistance == -1) {bestLeft = left;bestRight = right;}}}// 移动较小高度的指针，保留较高边界if (s[left] < s[right]) {left++;} else {right--;}}// 输出结果if (maxWater <= 0) {System.out.println(0);} else {System.out.println(bestLeft + " " + bestRight + ":" + maxWater);}}
}

---

代码详细解析

1. 输入处理：

   • 读取输入并转换为整数数组 s。
   • 处理长度为 1 的特殊情况（无法形成蓄水区间）。

2. 前缀和数组：

   • preSum[i] 表示前 i 个元素的总和，用于快速计算任意区间和。

3. 双指针遍历：

   • left 和 right 初始指向数组两端。
   • minH 计算当前左右边界的最小高度。
   • count 表示中间山脉的数量，sumMiddle 通过前缀和数组快速求得。

4. 蓄水量计算：

   • water = minH * count - sumMiddle 直接计算当前区间的蓄水量。
   • 维护 maxWater 和对应的最优边界 bestLeft 和 bestRight。

5. 指针移动策略：

   • 移动较小高度的指针，保留较高的边界以探索更大的蓄水量。

6. 结果输出：

   • 根据 maxWater 决定输出格式，处理无效解（结果 ≤ 0）。

---

综合分析

1. 时间复杂度：双指针法将时间复杂度从 O(n²) 优化到 O(n)，适用于大规模数据（n ≤ 10000）。
2. 空间复杂度：仅需 O(n) 空间存储前缀和数组。
3. 正确性保障：
   • 前缀和数组确保区间和计算的快速和准确。
   • 指针移动策略保留较高边界，最大化后续探索的潜力。
   • 处理多个解时，优先选择下标距离更近的边界。

---

python

题目分析

题目要求在给定的山脉数组中选择两个边界，使得它们之间的蓄水量最大。蓄水量计算公式为：两边界高度的最小值 × 区间长度 - 中间山脉的总高度。需要处理以下关键点：

1. 高效计算：避免暴力枚举所有可能的左右边界（O(n²) 时间复杂度），采用双指针法实现 O(n) 时间复杂度。
2. 边界条件：处理无法蓄水的情况（结果 ≤ 0）和多个解时选择下标距离最近的边界。
3. 数据预处理：使用前缀和数组快速计算中间山脉的总高度。

---

解决思路

1. 双指针法：初始化左右指针分别指向数组首尾，每次移动较小高度的指针，保留较大高度的边界以探索更大蓄水量。
2. 前缀和优化：预处理前缀和数组，实现区间和 O(1) 查询。
3. 条件判断：维护最大蓄水量及对应的左右边界，处理距离更短的解。

---

Python 代码实现

def main():# 读取输入并转换为整数数组s = list(map(int, input().strip().split()))n = len(s)# 处理特殊情况：数组长度不足时无法形成蓄水区间if n < 2:print(0)return# 构建前缀和数组 pre_sum，pre_sum[i] 表示前i个元素的总和pre_sum = [0] * (n + 1)for i in range(n):pre_sum[i + 1] = pre_sum[i] + s[i]# 初始化双指针和最大值变量left, right = 0, n - 1max_water = 0best_left, best_right = -1, -1while left < right:# 当前左右边界的高度min_h = min(s[left], s[right])# 中间山脉的数量（区间长度为 right - left - 1）count = right - left - 1if count > 0:  # 仅当区间内有元素时计算蓄水量# 计算中间山脉的总高度：前缀和差法sum_middle = pre_sum[right] - pre_sum[left + 1]# 当前蓄水量 = 容器高度 × 区间长度 - 中间总高度current_water = min_h * count - sum_middle# 如果当前蓄水量更大，更新最大值和最优边界if current_water > max_water:max_water = current_waterbest_left, best_right = left, right# 如果蓄水量相同，但区间更短，则更新最优边界elif current_water == max_water:current_distance = right - leftbest_distance = best_right - best_leftif current_distance < best_distance or best_distance == -1:best_left, best_right = left, right# 移动指针策略：保留较高的边界，移动较矮的一边if s[left] < s[right]:left += 1</