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

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

news 2025/4/19 14:34:53

在这里插入图片描述

2025 A卷 200分 题型

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

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

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

目录

    • 题目名称：天然蓄水库
      • 题目描述
      • 示例
    • Java
      • 题目分析
      • 解决思路
      • Java 代码实现
      • 代码详细解析
      • 综合分析
    • python
      • 题目分析
      • 解决思路
      • Python 代码实现
      • 代码详细解析
      • 关键逻辑图解
      • 综合分析
    • JavaScript
      • 题目分析
      • JavaScript 代码实现
      • 代码详细解析
      • 综合分析
      • 示例测试
        • 示例1：
        • 示例2：
      • 总结
    • C++
      • 解决思路
      • 代码实现
      • 关键步骤解析
      • 正确性验证
    • C语言
      • 解决思路
      • 代码实现
      • 代码详细解析
      • 复杂度与优化
      • 示例测试
    • GO
      • 题目分析
      • Go 代码实现
      • 代码详细解析
      • 示例验证
        • 输入1：
        • 输出1：
      • 时间复杂度与优化
      • 边界处理
      • 综合分析
    • 更多内容：

题目名称：天然蓄水库

  • 知识点：双指针
  • 时间限制：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 += 1else:right -= 1# 输出结果if max_water <= 0:print(0)else:# 注意输出的是原数组下标，不需要调整print(f"{best_left} {best_right}:{max_water}")if __name__ == "__main__":main()

代码详细解析

def main():# 读取输入并转换为整数数组s = list(map(int, input().strip().split()))  # 例如输入 "1 9 6 2 5" → [1,9,6,2,5]n = len(s)  # 数组长度# 处理特殊情况：数组长度不足时无法形成蓄水区间if n < 2:print(0)  # 直接输出0return     # 结束函数# 构建前缀和数组 pre_sum，pre_sum[i] 表示前i个元素的总和pre_sum = [0] * (n + 1)  # 初始化长度为n+1的数组，初始值全0for i in range(n):       # 遍历原数组pre_sum[i + 1] = pre_sum[i] + s[i]  # 前i+1项和 = 前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       # 例如区间 [2,5] 中间有元素3、4，数量为2if count > 0:  # 仅当区间内有元素时计算蓄水量# 计算中间山脉的总高度：前缀和差法sum_middle = pre_sum[right] - pre_sum[left + 1]  # [left+1, right-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 - left    # 当前区间距离best_distance = best_right - best_left  # 历史最优区间距离# 如果当前区间更短，或者尚未记录最优解（初始为-1）if current_distance < best_distance or best_distance == -1:best_left, best_right = left, right# 移动指针策略：保留较高的边界，移动较矮的一边if s[left] < s[right]:  # 左边界较矮left += 1           # 左指针右移，尝试寻找更高的左边界else:                    # 右边界较矮或相等right -= 1          # 右指针左移，尝试寻找更高的右边界# 输出结果if max_water <= 0:  # 无效蓄水（可能所有区间计算值≤0）print(0)else:# 注意输出的是原数组下标，不需要调整（Python列表索引从0开始）print(f"{best_left} {best_right}:{max_water}")

关键逻辑图解

假设输入为 s = [1, 9, 6, 2, 5, 4, 9, 3, 7]，最优解为 s[1] 和 s[6]：

  1. 初始化指针：left=0, right=8（对应高度1和7）

    • 计算 min_h = min(1,7) = 1
    • 中间元素数量 count = 8-0-1 = 7
    • 中间总和 sum_middle = sum(s[1]~s[7]) = 9+6+2+5+4+9+3 = 38
    • 蓄水量 1*7 - 38 = -31（无效）

  2. 移动左指针（因为左边界较矮）→ left=1（高度9）

    • 现在 left=1, right=8（高度9和7）
    • min_h = min(9,7) = 7
    • 中间元素数量 count = 8-1-1 = 6
    • 中间总和 sum(s[2]~s[7]) = 6+2+5+4+9+3 = 29
    • 蓄水量 7*6 -29 = 42-29=13（有效）

  3. 继续移动右指针（右边界较矮）→ 逐步收敛，直到找到最优解。

综合分析

  1. 时间复杂度 O(n)：双指针仅遍历一次数组。
  2. 空间复杂度 O(n)：仅需存储前缀和数组。
  3. 处理多个解的正确性：当蓄水量相同时，优先选择下标距离更近的边界。
  4. 健壮性：处理无效输入和边界条件（如数组长度为1）。

JavaScript

题目分析

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

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

JavaScript 代码实现

const readline = require('readline');const rl = readline.createInterface({input: process.stdin,output: process.stdout
});rl.on('line', (input) => {const s = input.trim().split(/\s+/).map(Number);const n = s.length;if (n < 2) {console.log(0);rl.close();return;}// 构建前缀和数组 preSum，preSum[i] 表示前i个元素的总和const preSum = new Array(n + 1).fill(0);for (let i = 0; i < n; i++) {preSum[i + 1] = preSum[i] + s[i];}let left = 0, right = n - 1;let maxWater = 0;let bestLeft = -1, bestRight = -1;while (left < right) {const minH = Math.min(s[left], s[right]);const count = right - left - 1;if (count > 0) {const sumMiddle = preSum[right] - preSum[left + 1];const currentWater = minH * count - sumMiddle;if (currentWater > maxWater) {maxWater = currentWater;bestLeft = left;bestRight = right;} else if (currentWater === maxWater) {const currentDistance = right - left;const bestDistance = bestRight - bestLeft;if (currentDistance < bestDistance || bestDistance === -1) {bestLeft = left;bestRight = right;}}}// 移动较小高度的指针if (s[left] < s[right]) {left++;} else {right--;}}if (maxWater <= 0) {console.log(0);} else {console.log(`${bestLeft} ${bestRight}:${maxWater}`);}rl.close();
});

代码详细解析

  1. 输入处理：

    const s = input.trim().split(/\s+/).map(Number);
    • 读取输入行，去除首尾空格，按空格分割为字符串数组，并转换为数字数组。

  2. 特殊情况处理：

    if (n < 2) {console.log(0);return;
}
    • 数组长度小于2时无法形成蓄水区间，直接输出0。

  3. 前缀和数组：

    const preSum = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {preSum[i + 1] = preSum[i] + s[i];
}
    • preSum[i] 存储前 i 个元素的总和，用于快速计算任意区间和。

  4. 双指针初始化：

    let left = 0, right = n - 1;
let maxWater = 0;
let bestLeft = -1, bestRight = -1;
    • left 和 right 初始指向数组两端，maxWater 记录最大蓄水量，bestLeft 和 bestRight 记录最优边界。

  5. 双指针遍历：

    while (left < right) {const minH = Math.min(s[left], s[right]);const count = right - left - 1;if (count > 0) {const sumMiddle = preSum[right] - preSum[left + 1];const currentWater = minH * count - sumMiddle;// 更新最大值或更优解}// 移动指针
}
    • 每次循环计算当前边界的蓄水量，并更新最优解。

  6. 蓄水量计算：

    const sumMiddle = preSum[right] - preSum[left + 1];
const currentWater = minH * count - sumMiddle;
    • sumMiddle 是中间山脉的总高度，currentWater 是当前蓄水量。

  7. 更新最优解：

    if (currentWater > maxWater) {maxWater = currentWater;bestLeft = left;bestRight = right;
} else if (currentWater === maxWater) {// 处理距离更近的情况
}
    • 当蓄水量相同时，优先选择下标距离更近的边界。

  8. 移动指针策略：

    if (s[left] < s[right]) {left++;
} else {right--;
}
    • 移动较小高度的指针，保留较高边界以探索更大蓄水量。

  9. 输出结果：

    if (maxWater <= 0) {console.log(0);
} else {console.log(`${bestLeft} ${bestRight}:${maxWater}`);
}
    • 根据最大蓄水量决定输出格式。

综合分析

  1. 时间复杂度 O(n)：双指针法确保每个元素仅被访问一次。
  2. 空间复杂度 O(n)：仅需存储前缀和数组，适用于大规模数据。
  3. 健壮性：
    • 前缀和数组避免重复计算区间和。
    • 处理输入格式和边界条件（如空输入、数组长度为1）。
  4. 正确性：
    • 当多个解蓄水量相同时，选择下标距离最近的边界。
    • 严格处理无效蓄水（结果 ≤ 0 时输出0）。

示例测试

示例1：

输入：1 9 6 2 5 4 9 3 7
输出：1 6:19

  • 左边界为 s[1]=9，右边界为 s[6]=9，中间总高度为 6+2+5+4=17，蓄水量为 9*4 -17=19。
示例2：

输入：3 2 1
输出：0

  • 任何两边界蓄水量均为负或零。

总结

通过双指针法和前缀和数组的结合，JavaScript 实现能够高效、准确地求解最大蓄水量问题。代码逻辑清晰，充分考虑了各种边界条件，是解决此类问题的最佳方案。

C++

解决思路

本问题要求在给定山脉数组中，选择两边界使蓄水量最大。蓄水量计算公式为：两边界高度的最小值 × 中间元素数量 - 中间山脉总高度。使用双指针法高效遍历可能解，结合前缀和数组快速计算区间和，确保时间复杂度为 O(n)。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <sstream>using namespace std;int main() {string line;getline(cin, line); // 读取整行输入istringstream iss(line); // 创建字符串流用于分割输入vector<int> s; // 存储山脉高度的数组int num;while (iss >> num) { // 解析每个整数s.push_back(num);}int n = s.size();if (n < 2) { // 处理长度不足的情况cout << 0 << endl;return 0;}// 构建前缀和数组，pre_sum[i]表示前i个元素的总和vector<int> pre_sum(n + 1, 0);for (int i = 0; i < n; ++i) {pre_sum[i + 1] = pre_sum[i] + s[i];}int left = 0, right = n - 1; // 双指针初始化int max_water = 0; // 最大蓄水量int best_left = -1, best_right = -1; // 最优解的左右边界while (left < right) {int minH = min(s[left], s[right]); // 当前边界的最小高度int count = right - left - 1; // 中间元素的数量if (count > 0) { // 仅当中间有元素时计算蓄水量int sum_middle = pre_sum[right] - pre_sum[left + 1]; // 中间山脉总高度int current_water = minH * count - sum_middle; // 当前蓄水量// 更新最大值或更优解（距离更近）if (current_water > max_water) {max_water = current_water;best_left = left;best_right = right;} else if (current_water == max_water) {int current_dist = right - left; // 当前区间距离int best_dist = best_right - best_left; // 历史最优区间距离if (best_left == -1 || current_dist < best_dist) {best_left = left;best_right = right;}}}// 移动较小高度的指针，保留较高边界以探索更大蓄水量if (s[left] < s[right]) {++left;} else {--right;}}// 输出结果if (max_water <= 0) {cout << 0 << endl;} else {cout << best_left << " " << best_right << ":" << max_water << endl;}return 0;
}

关键步骤解析

  1. 输入处理：读取输入行并解析为整数数组。
  2. 前缀和数组：预处理前缀和数组 pre_sum，用于快速计算任意区间和。
  3. 双指针遍历：
    • 初始化左右指针 left 和 right，分别指向数组首尾。
    • 计算当前边界的较小高度 minH 和中间元素数量 count。
    • 利用前缀和数组计算中间山脉总高度 sum_middle，进而得到当前蓄水量 current_water。
  4. 更新最优解：维护最大蓄水量 max_water 及对应的边界，确保在蓄水量相同时选择距离更近的边界。
  5. 指针移动策略：移动较小高度的指针，保留较高边界以探索更大的蓄水量。
  6. 结果输出：根据最大蓄水量决定输出格式，处理无效解。

正确性验证

通过双指针法和前缀和数组的结合，确保在 O(n) 时间复杂度内找到最优解。双指针策略保留较高边界，确保不会错过潜在的最大蓄水量组合。前缀和数组优化区间和计算，保证效率。示例测试验证代码正确性，覆盖各种边界条件。

C语言

解决思路

题目要求在给定山脉数组中找出两个边界，使蓄水量最大。蓄水量计算公式为：两边界高度最小值 × 中间元素数量 - 中间山脉总高度。采用双指针法遍历所有可能的边界组合，结合前缀和数组优化计算效率。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>#define INITIAL_CAPACITY 10int main() {char line[100000]; // 输入缓冲区fgets(line, sizeof(line), stdin); // 读取输入行// 动态数组存储山脉高度int *s = (int *)malloc(INITIAL_CAPACITY * sizeof(int));int capacity = INITIAL_CAPACITY;int n = 0; // 数组长度// 分割输入字符串为整数数组char *token = strtok(line, " \n");while (token != NULL) {// 动态扩容if (n >= capacity) {capacity *= 2;s = (int *)realloc(s, capacity * sizeof(int));}s[n++] = atoi(token);token = strtok(NULL, " \n");}// 处理长度不足的情况if (n < 2) {printf("0\n");free(s);return 0;}// 构建前缀和数组int *pre_sum = (int *)malloc((n + 1) * sizeof(int));pre_sum[0] = 0;for (int i = 0; i < n; i++) {pre_sum[i + 1] = pre_sum[i] + s[i];}// 双指针初始化int left = 0, right = n - 1;int max_water = 0;int best_left = -1, best_right = -1;// 双指针遍历逻辑while (left < right) {int minH = s[left] < s[right] ? s[left] : s[right];int count = right - left - 1;if (count > 0) {int sum_middle = pre_sum[right] - pre_sum[left + 1];int current_water = minH * count - sum_middle;// 更新最大值或更优解if (current_water > max_water) {max_water = current_water;best_left = left;best_right = right;} else if (current_water == max_water) {int current_dist = right - left;int best_dist = best_right - best_left;if (best_left == -1 || current_dist < best_dist) {best_left = left;best_right = right;}}}// 移动较小高度的指针if (s[left] < s[right]) {left++;} else {right--;}}// 输出结果if (max_water <= 0) {printf("0\n");} else {printf("%d %d:%d\n", best_left, best_right, max_water);}// 释放动态内存free(s);free(pre_sum);return 0;
}

代码详细解析

  1. 输入处理

    char line[100000];
fgets(line, sizeof(line), stdin);
    • 创建缓冲区读取整行输入，支持最长 100,000 字符。

  2. 动态数组初始化

    int *s = (int *)malloc(INITIAL_CAPACITY * sizeof(int));
int capacity = INITIAL_CAPACITY;
    • 初始分配容量为 10 的数组，避免频繁扩容。

  3. 分割字符串为整数

    char *token = strtok(line, " \n");
while (token != NULL) {// 动态扩容if (n >= capacity) {capacity *= 2;s = realloc(s, capacity * sizeof(int));}s[n++] = atoi(token);token = strtok(NULL, " \n");
}
    • 使用 strtok 按空格和换行符分割字符串。
    • 动态扩容策略：容量不足时翻倍，保证插入效率。

  4. 前缀和数组构建

    int *pre_sum = malloc((n + 1) * sizeof(int));
pre_sum[0] = 0;
for (int i = 0; i < n; i++) {pre_sum[i + 1] = pre_sum[i] + s[i];
}
    • pre_sum[i] 存储前 i 个元素的和，快速计算任意区间和。

  5. 双指针核心逻辑

    while (left < right) {int minH = s[left] < s[right] ? s[left] : s[right];int count = right - left - 1;if (count > 0) {int sum_middle = pre_sum[right] - pre_sum[left + 1];int current_water = minH * count - sum_middle;// 更新最大值或更优解if (...) { ... }}// 移动指针if (...) { ... }
}
    • 每次循环计算当前边界的蓄水量。
    • 移动较小高度的指针，保留较大边界以探索更大蓄水量。

  6. 释放内存

    free(s);
free(pre_sum);
    • 避免内存泄漏，确保程序健壮性。

复杂度与优化

  • 时间复杂度：O(n)，双指针遍历数组一次。
  • 空间复杂度：O(n)，用于存储山脉数组和前缀和数组。
  • 优势：通过双指针法和前缀和数组的结合，在保证效率的同时代码简洁清晰。

示例测试

  • 输入1：1 9 6 2 5 4 9 3 7

    • 输出：1 6:19
    • 解释：选择 s[1]（高9）和 s[6]（高9），中间山脉总高度为 6+2+5+4=17，蓄水量为 9×4 -17=19。

  • 输入2：3 2 1

    • 输出：0
    • 解释：所有可能的边界组合蓄水量 ≤0。

GO

题目分析

题目要求在给定山脉数组中找到两边界，使得蓄水量最大。蓄水量计算公式为：两边界高度的最小值 × 区间长度 - 中间山脉总高度。通过双指针法高效遍历所有可能的边界组合，确保时间复杂度为 O(n)。

Go 代码实现

package mainimport ("bufio""fmt""os""strconv""strings"
)func main() {// 读取输入行并分割为字符串数组scanner := bufio.NewScanner(os.Stdin)scanner.Scan()input := strings.TrimSpace(scanner.Text())strArr := strings.Fields(input)// 转换为整数数组var s []intfor _, str := range strArr {num, _ := strconv.Atoi(str)s = append(s, num)}n := len(s)// 处理数组长度不足的情况if n < 2 {fmt.Println(0)return}// 构建前缀和数组 preSumpreSum := make([]int, n+1)for i := 0; i < n; i++ {preSum[i+1] = preSum[i] + s[i]}// 双指针初始化left, right := 0, n-1maxWater := 0bestLeft, bestRight := -1, -1// 双指针遍历逻辑for left < right {minH := min(s[left], s[right])count := right - left - 1if count > 0 {sumMiddle := preSum[right] - preSum[left+1]currentWater := minH*count - sumMiddle// 更新最大值或更优解if currentWater > maxWater {maxWater = currentWaterbestLeft, bestRight = left, right} else if currentWater == maxWater {currentDist := right - leftbestDist := bestRight - bestLeftif bestLeft == -1 || currentDist < bestDist {bestLeft, bestRight = left, right}}}// 移动较小高度的指针if s[left] < s[right] {left++} else {right--}}// 输出结果if maxWater <= 0 {fmt.Println(0)} else {fmt.Printf("%d %d:%d\n", bestLeft, bestRight, maxWater)}
}// 辅助函数：获取两个整数的最小值
func min(a, b int) int {if a < b {return a}return b
}

代码详细解析

// 读取输入
scanner := bufio.NewScanner(os.Stdin)
scanner.Scan()
input := strings.TrimSpace(scanner.Text())
  • bufio.Scanner 读取标准输入的一行数据，TrimSpace 去除首尾空格。
// 转换为整数数组
strArr := strings.Fields(input)
var s []int
for _, str := range strArr {num, _ := strconv.Atoi(str)s = append(s, num)
}
  • strings.Fields 按空格分割字符串为数组。
  • strconv.Atoi 将字符串转为整数，并存入动态切片 s。
// 前缀和数组
preSum := make([]int, n+1)
for i := 0; i < n; i++ {preSum[i+1] = preSum[i] + s[i]
}
  • preSum[i+1] 存储前 i 个元素的总和，例如 preSum[3] = s[0]+s[1]+s[2]。
// 双指针核心逻辑
for left < right {minH := min(s[left], s[right])count := right - left - 1if count > 0 {sumMiddle := preSum[right] - preSum[left+1]currentWater := minH*count - sumMiddle// 更新最优解if currentWater > maxWater {maxWater = currentWaterbestLeft, bestRight = left, right} else if currentWater == maxWater {// 选择下标距离更近的解if right-left < bestRight-bestLeft {bestLeft, bestRight = left, right}}}// 移动指针if s[left] < s[right] {left++} else {right--}
}
  • 双指针移动策略：每次移动较矮的边界，保留较高的边界以探索更大的蓄水量。
  • 蓄水量计算：minH * count 是理想容器体积，sumMiddle 是实际山脉体积，差值即蓄水量。

示例验证

输入1：
1 9 6 2 5 4 9 3 7
  • 解析：
    • 左右指针初始指向 0 和 8（值 1 和 7）。
    • 逐步移动左指针到 1（值 9），右指针到 6（值 9）。
    • 中间山脉总高度 = 6 + 2 + 5 + 4 = 17。
    • 蓄水量 = 9×4 - 17 = 19。
输出1：
1 6:19

时间复杂度与优化

  • 时间复杂度：O(n)，双指针遍历数组一次。
  • 空间复杂度：O(n)，用于存储前缀和数组。
  • 优势：
    • 双指针法避免暴力枚举所有 O(n²) 组合。
    • 前缀和数组实现区间和 O(1) 查询。

边界处理

  • 数组长度 < 2：直接返回 0。
  • 所有蓄水量 ≤ 0：输出 0。
  • 多解选择：蓄水量相同时优先选择下标距离更近的边界。

综合分析

  1. 高效性：双指针法在 O(n) 时间内解决问题。
  2. 代码简洁：利用 Go 的切片和内置函数简化输入处理。
  3. 健壮性：正确处理所有边界条件和多解场景。
  4. 易读性：通过清晰的变量命名和逻辑分段，代码易于理解和维护。

更多内容：

https://www.kdocs.cn/l/cvk0eoGYucWA

本文发表于【纪元A梦】，关注我，获取更多实用教程/资源！


http://www.mrgr.cn/news/98748.html

相关文章：

  • 猫咪如厕检测与分类识别系统系列【九】视频检测区域在线绘制+支持摄像头+网络摄像头+整体构建【上】
  • Web三漏洞学习（其二：sql注入）
  • 树莓派超全系列教程文档--(28)boot文件夹内容
  • 【论文阅读】UniAD: Planning-oriented Autonomous Driving
  • 虚幻引擎5-Unreal Engine笔记之“将MyStudent变量设置为一个BP_Student的实例”这句话如何理解？
  • 华为OD机试真题——硬件产品销售方案（2025A卷：100分）Java/python/JavaScript/C++/C语言/GO六种最佳实现
  • 【Java学习笔记】运算符
  • oracle查询锁表和解锁
  • 理解计算篇--正则表达式转NFA--理论部分
  • 【Java学习笔记】数据类型转换
  • Linux-ftp tftp vsftpd区别
  • 11-算法打卡-链表-删除链表的倒数第N个节点-leetcode(19)-第十一天
  • Redis高频面试题（含答案）
  • uniapp-商城-27-vuex 通用方法
  • MGR实现mysql高可用性
  • 4G/5G模组----概念+驱动+调试
  • 【八股】计算机网络
  • 日语学习-日语知识点小记-构建基础-JLPT-N4阶段（5）：できます 完成了等 しか。。。ない 只有
  • 什么是进程？
  • 【回眸】Tessy集成测试软件使用指南（一）新手使用篇