全网最全面的华为OD机试真题汇总，100%原题题库，不需要开会员即可查看全部内容，更多考题请查看真题库。
真题库：https://www.yuque.com/codernav.com/od
题目：天然蓄水库
知识点双指针
时间限制：1s 空间限制：256MB 限定语言：不限
题目描述：
描述：
公元2919年，人类终于发现了一颗宜居星球——X星。现想在X星一片连绵起伏的山脉间建一个天热蓄水库，如何选取水库边界，使蓄水量最大？
要求：
山脉用正整数数组s表示，每个元素代表山脉的高度。
选取山脉上两个点作为蓄水库的边界，则边界内的区域可以蓄水，蓄水量需排除山脉占用的空间
蓄水量的高度为两边界的最小值。
如果出现多个满足条件的边界，应选取距离最近的一组边界。
输出边界下标（从0开始）和最大蓄水量；如果无法蓄水，则返回0，此时不返回边界。
例如，当山脉为s=[3,1,2]时，则选取s[0]和s[2]作为水库边界，则蓄水量为1，此时输出：0 2:1
当山脉s=[3,2,1]时，不存在合理的边界，此时输出：0。
输入描述：
一行正整数，用空格隔开，例如输入
1 2 3
表示s=[1,2,3]
输出描述：
当存在合理的水库边界时，输出左边界、空格、右边界、英文冒号、蓄水量；例如
0 2:1
当不存在合理的书库边界时，输出0；例如
0
补充说明：
数组s满足：
1 <= length(s) <= 10000
0 <= s[i] <= 10000
示例1
输入：
1 9 6 2 5 4 9 3 7
输出：
1 6:19
说明：
经过分析，选取s[1]和s[6]时，水库蓄水量为19（3+7+4+5）
示例2
输入：
1 8 6 2 5 4 8 3 7
输出：
1 6:15
说明：
经过分析，选取s[1]和s[8]时，水库蓄水量为15；同样选取s[1]和s[6]时，水库蓄水量也为15。由于后者下标距离小（为5），故应选取后者。
示例3
输入：
1 2 3
输出：
0
说明：
不存在合理的水库边界。
真机测试用例：
1 1 2 3 0
4 1 8 6 2 5 4 8 3 7 1 6:15
6 1 7 3 10 10 1 3:4
7 4 3 2 0 2 3 1 5:5
8 1 2 2 0 2 1 2 0 2 2 2 8:5
解题思路：
代码实现一：
package com.codernav.demo.hwod.exam;
import java.util.Arrays;
import java.util.Scanner;
/**
* @title 天然蓄水库
* @Description 公元2919年，人类终于发现了一颗宜居星球——X星。现想在X星一片连绵起伏的山脉间建一个天热蓄水库，如何选取水库边界，使蓄水量最大？
* 要求：
* 山脉用正整数数组s表示，每个元素代表山脉的高度。
* 选取山脉上两个点作为蓄水库的边界，则边界内的区域可以蓄水，蓄水量需排除山脉占用的空间
* 蓄水量的高度为两边界的最小值。
* 如果出现多个满足条件的边界，应选取距离最近的一组边界。
* 输出边界下标（从0开始）和最大蓄水量；如果无法蓄水，则返回0，此时不返回边界。
* 例如，当山脉为s=[3,1,2]时，则选取s[0]和s[2]作为水库边界，则蓄水量为1，此时输出：0 2:1
* 当山脉s=[3,2,1]时，不存在合理的边界，此时输出：0。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/28
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] strings = sc.nextLine().split(" ");
int[] mountains = Arrays.stream(strings).mapToInt(Integer::parseInt).toArray();
int min = Arrays.stream(mountains).min().getAsInt(); //最小山峰
int max = 0; //最大面积
int maxLeft = 0; //左边界
int maxRight = 0; //右边界
for (int i = 0; i < mountains.length - 2; i++) {
int left = mountains[i];
if (left == min) { //最小山峰为边界无法构成蓄水池
continue;
}
for (int j = i + 2; j < mountains.length; j++) {
int right = mountains[j];
if (right == min) { //最小山峰为边界无法构成蓄水池
continue;
}
int height = Math.min(left, right); //蓄水池的高度为边界最小值
int area = 0; //蓄水池面积
for (int k = i + 1; k < j; k++) {
int areaOne = height - mountains[k]; //当前山峰的蓄水量
if (areaOne > 0) { //蓄水量大于0则表示可以蓄水
area += areaOne;
}
}
if (area > max) { //此时面积最大
max = area;
maxLeft = i;
maxRight = j;
} else if (area == max && (maxRight - maxLeft) > (j - i)) { //面积相等距离较近
maxLeft = i;
maxRight = j;
}
}
}
System.out.println(max == 0 ? 0 : maxLeft + " " + maxRight + ":" + max);
}
}
代码实现二：满分Java代码实现
package com.codernav.demo.hwod.exam;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
/**
* @title 天然蓄水库
* @Description 公元2919年，人类终于发现了一颗宜居星球——X星。现想在X星一片连绵起伏的山脉间建一个天热蓄水库，如何选取水库边界，使蓄水量最大？
* 要求：
* 山脉用正整数数组s表示，每个元素代表山脉的高度。
* 选取山脉上两个点作为蓄水库的边界，则边界内的区域可以蓄水，蓄水量需排除山脉占用的空间
* 蓄水量的高度为两边界的最小值。
* 如果出现多个满足条件的边界，应选取距离最近的一组边界。
* 输出边界下标（从0开始）和最大蓄水量；如果无法蓄水，则返回0，此时不返回边界。
* 例如，当山脉为s=[3,1,2]时，则选取s[0]和s[2]作为水库边界，则蓄水量为1，此时输出：0 2:1
* 当山脉s=[3,2,1]时，不存在合理的边界，此时输出：0。
* @Author 开发者导航
* @website https://codernav.com
* @date 2023/5/28
*/
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
//山脉的高度数组
Integer[] height = Arrays.stream(input.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);
int n = height.length;
//左侧最高山脉数组
int[] left = new int[n];
for (int i = 1; i < n; i++) {
//i左侧的最高山脉
left[i] = Math.max(left[i - 1], height[i - 1]);
}
//右侧最高山脉数组
int[] right = new int[n];
for (int i = n - 2; i >= 0; i--) {
//i右侧的最高山脉
right[i] = Math.max(right[i + 1], height[i + 1]);
}
//最大蓄水高度跟山脉的总高度数组
int[] waterheight = new int[n];
HashSet<Integer> waters_h = new HashSet<>();
for (int i = 1; i < n - 1; i++) {
//当前山脉的最大蓄水量
int wat = Math.max(0, Math.min(left[i], right[i]) - height[i]);
if (wat != 0) {
//最大蓄水量的高度+山脉的高度
waterheight[i] = wat + height[i];
waters_h.add(waterheight[i]);
}
}
int[] result = new int[3];
for (int sig : waters_h) {
//左侧第一个满足条件的山脉
int l = 0;
while (waterheight[l] < sig || height[l] >= sig) {
l++;
}
//右侧第一个满足条件的山脉
int r = n - 1;
while (waterheight[r] < sig || height[r] >= sig) {
r--;
}
//蓄水量求和
int total_wat = 0;
for (int i = l; i <= r; i++) {
total_wat += Math.max(0, sig - height[i]);
}
if (total_wat > result[2]) {
//蓄水量大于之前的最大蓄水量则重置左右山脉索引和最大蓄水量
result[0] = l - 1;
result[1] = r + 1;
result[2] = total_wat;
} else if (total_wat == result[2]) {
//蓄水量等于之前最大蓄水量则判断其山脉距离，选其距离较小的
int d = r - l + 1;
int d2 = result[1] - result[0] - 1;
if (d < d2) {
result[0] = l - 1;
result[1] = r + 1;
}
}
}
if (result[2] == 0) {
System.out.print(0);
} else {
System.out.print(result[0]);
System.out.print(" ");
System.out.print(result[1]);
System.out.print(":");
System.out.print(result[2]);
}
}
}
相关文章
