首页 > 代码库 > LeetCode 42 Trapping Rain Water（积水体积）
LeetCode 42 Trapping Rain Water（积水体积）
题目链接： https://leetcode.com/problems/trapping-rain-water/?tab=Description
Problem: 根据所给数组的值，按照上图的示意图。求解积水最大体积。
首先对所给数组进行遍历操作，求出最大高度所对应的下标为maxIndex
之后从左向右进行遍历，设置左边高度为leftMax 并初始化为 height[0],从i==1到i==maxIndex进行遍历。不断更新water，以及leftMax
当height[I]小于leftMax时，water += leftMax - height
当height[i]大于leftMax时，leftMax = height[I]
之后从i==height.length - 2到下标 I == maxIndex进行遍历操作 初始化rightMax = height[height.length-1]
当height[I]小于rightMax时，water+=rightMax - height[I]
当height[I]大于rightMax时，rightMax = height[I]
函数结果返回water
参考代码：
package leetcode_50;/*** * * @author pengfei_zheng * 求积水的体积 */public class Solution42 { public static int trap(int[] height) { if (height.length <= 2) return 0; int max = -1; int maxIndex = 0; for (int i = 0; i < height.length; i++) { if (height[i] > max) { max = height[i]; maxIndex = i; } } int leftMax = height[0]; int water = 0; for (int i = 1; i < maxIndex; i++) { if (height[i] > leftMax) { leftMax = height[i]; } else { water += leftMax - height[i]; } } int rightMax = height[height.length - 1]; for (int i= height.length - 2; i > maxIndex; i--) { if (height[i] > rightMax) { rightMax = height[i]; } else { water += rightMax - height[i]; } } return water; } public static void main(String[]args){// int []height={0,1,0,2,1,0,1,3,2,1,2,1}; int []height={10,0,11,0,10}; System.out.println(trap(height)); }}
LeetCode 42 Trapping Rain Water（积水体积）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。