本文共 1133 字，大约阅读时间需要 3 分钟。

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]

输出：6

解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]

输出：9

解题思路：从单个i入手，对于位置i能装下多少水呢？

可以分析得到位置i能装两格水。

为什么位置i最多能盛2格水呢？因为，位置i能达到的水柱高度和其左边的最高柱子、右边的最高柱子有关，我们称之为这两个柱子高度为l_max和r_max;位置i的最大水柱高度就是min(l_max,r_max).其能够盛水最多为min(l_max,r_max)-height[i]。

解题思路，对其遍历的过程中，同时找其左最大和右最大。

public int trap(int[] height) {
   	    	// 暴力破解法	    	int res = 0;	    	// 对其遍历 第一个和最后一个都没法盛水	    	for(int i=1;i
   
    =0;j--) {
   	    			left_max = Math.max(height[i], left_max);	    		}	    			    		// 开始找right的max	    		for(int j=i;j
   

解题思路2：先申请两数组，记录好对应i的最大和最小值。

public int trap_2(int[] height) {
   	    	// 记录结果	    	int res = 0;	    	// 先计算最大和最小值	    	int[] left_max = new int[height.length];	    	int[] right_max = new int[height.length];	    	// 考虑边界的两个i值对其赋初值	    	left_max[0] = height[0];	    	right_max[height.length-1] = height[height.length-1];	    	// 计算	    	for(int i=1;i
   
    =0;i++) {
   	    		right_max[i] = Math.max(height[i], right_max[i+1]);	    	}	    	// 对能盛水的i遍历	    	for(int i=1;i
   

转载地址：https://codingchaozhang.blog.csdn.net/article/details/111461903 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！