华为OD机试真题——天然蓄水库（2025A卷：200分）Java/python/JavaScript/C++/C语言/GO六种最佳实现

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 - 1
    max_water = 0
    best_left, best_right = -1, -1
    
    while left < right:
        # 当前左右边界的高度
        min_h = min(s[left], s[right])
        # 中间山脉的数量（区间长度为 right - left - 1）
        count = right - left - 1
        
        if 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_water
                best_left, best_right = left, right
            # 如果蓄水量相同，但区间更短，则更新最优边界
            elif current_water == max_water:
                current_distance = right - left
                best_distance = best_right - best_left
                if current_distance < best_distance or best_distance == -1:
                    best_left, best_right = left, right
        
        # 移动指针策略：保留较高的边界，移动较矮的一边
        if s[left] < s[right]:
            left += 1</