题目
给出 n 个非负整数，代表一张X轴上每个区域宽度为 1 的海拔图, 计算这个海拔图最多能接住多少（面积）雨水。
输入
[0,1,0,2,1,0,1,3,2,1,2,1]
输出
6
解题思路
先遍历找到海拔最高值和最高值的位置；从最左端走到最高点，海拔下降时计算水位，水位 = （左边最近比自己高的海拔 - 自身海拔）*1，遇到更高的海拔时更新海拔；从最右端走到最高点，海拔下降时计算水位，水位 = （右边最近比自己高的海拔 - 自身海拔）*1，遇到更高海拔时更新海拔；
实现代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.nextLine();
String[] s1 = s.substring(1,s.length()-1).split(",");
int[] h = new int[s1.length];
for(int i=0; i<s1.length; i++){
h[i] = Integer.parseInt(s1[i]);
}
int area = getMaxArea(h); // 获取雨水量
System.out.println(area);
}
public static int getMaxArea(int[] a){
int l = 0, r = a.length-1, maxh = 0, maxh_index = 0, area = 0;
for(int i=0; i<a.length; i++){ // 找到最高海拔值和最高海拔位置
if(a[i] > maxh){
maxh = a[i];
maxh_index = i;
}
}
// 计算雨水量
int now_h = a[0];
for(int j=0; j<maxh_index; j++){
if(now_h<a[j]){
now_h = a[j];
}else{
area += (now_h - a[j]);
}
}
int now_h2 = a[a.length-1];
for(int k=a.length-1; k>maxh_index; k--){
if(now_h2<a[k]){
now_h2 = a[k];
}else{
area += (now_h2 - a[k]);
}
}
return area;
}
}
转载于:https://www.cnblogs.com/paopaolx/p/11486748.html
