LC 42.接雨水
创始人
2024-11-15 14:04:19
0

42.接雨水

给定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

提示:

  • n = = h e i g h t . l e n g t h n == height.length n==height.length
  • 1 ≤ n ≤ 2 ∗ 1 0 4 1 \leq n \leq 2 * 10^4 1≤n≤2∗104
  • 0 ≤ h e i g h t [ i ] ≤ 1 0 5 0 \leq height[i] \leq 10^5 0≤height[i]≤105

解法一(双指针)

思路分析

  1. 对于下雨之后能接多少雨水, 取决于凹槽的数量以及每个凹槽的容量; 而凹槽的容量是由左右边界的最小值以及左右边界长度决定的;

  2. 可以使用左右指针分别指向数组左右边界, 分别移动左右指针来计算接水量;

  3. 当两边柱子有一端更高时, 假设在右端, 如下图所示, 则此时积水的高度依赖于从左到右方向; 计算积水量应该从左到右进行计算; 左端柱子更高时同理;
    在这里插入图片描述
    在这里插入图片描述

  4. 所以在左右指针指向的柱子之间, 若左指针指向的柱子小于右指针指向的柱子, 则应该移动左指针, 反之应该移动右指针;

  5. 使用leftMax变量来记录左指针左边柱子的最大值, 当左指针所在柱子高度高于左边柱子最大值时, 说明左指针柱子处无法接到雨水, 则跳过并更新最大值, 且左指针继续向右移动;

  6. 同理, 使用rightMax变量记录右指针右边柱子的最大值, 当右指针所在柱子高度高于右边柱子最大值时, 右指针柱子无法接到雨水, 则跳过并更新最大值, 且右指针继续向左移动;

实现代码

class Solution { 	// 双指针     public int trap(int[] height) { 		// 初始化 		int ans = 0; 		// 左、右指针 分别指向最左边界、最右边界 		int left = 0, right = height.length-1; 		// 左边界最大值 		int leftMax = 0; 		// 右边界最大值 		int rightMax = 0; 		while (left < right) { 			if (height[left] < height[right]) { 				// 若左边界高度低于右边界高度 则说明凹槽高度以左边界为准 				if (height[left] > leftMax) { 					// 当此时左边界高度大于 左边界最大值时 无法形成凹槽 所以不计算雨水量 					// 更新左边界 					leftMax = height[left]; 				} else { 					// 左边界高度低于 最大值 则说明该处可以接到雨水 计算雨水量 					ans += leftMax - height[left]; 				} 				// 移动左边界 				++ left; 			} else { 				if (height[right] > rightMax) { 					rightMax = height[right]; 				} else { 					ans += rightMax - height[right]; 				} 				-- right; 			} 		} 		return ans;     } } 

提交结果

解答成功:

执行耗时:0 ms,击败了100.00% 的Java用户

内存消耗:45.7 MB,击败了5.13% 的Java用户

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( 1 ) O(1) O(1)

相关内容

热门资讯

教程攻略!全民牛牛科技app(... 相信很多朋友都在电脑上玩过全民牛牛科技app吧,但是很多朋友都在抱怨用电脑玩起来不方便。为此小编给大...
透视了解!wpk俱乐部有外挂的... 您好,德扑之星这款游戏可以开挂的,确实是有挂的,需要了解加微【841106723】很多玩家在这款游戏...
4分钟数据!wepoker轻量... 4分钟数据!wepoker轻量版透视方法(透视)脚本辅助透视免费(有挂靠谱)-详细教程是一款可以让一...
八分钟俱乐部!德州伙牌怎么打稳... 《hhpoker软件透明挂》是一款多人竞技的hhpoker辅助透视游戏,你将微扑克对手来到同一个战场...
透明新版!德州之星软件,扑克世... 透明新版!德州之星软件,扑克世界辅助下载,wepoker作弊视频(有挂原理);相信小伙伴都知道这个德...
一分钟带你了解!江西中至游戏辅... 一分钟带你了解!江西中至游戏辅助(透明挂)外挂透明挂辅助软件(2022已更新)(哔哩哔哩)是一款可以...
七分钟盈利!Hhpoker能开... 七分钟盈利!Hhpoker能开挂吗,wepoker到底有透视,细节方法(有挂秘诀);亲,有的,ai轻...
5分钟下载!hhpoker破解... 5分钟下载!hhpoker破解工具(透视)透视作弊辅助APP(有挂详细)-详细教程;1、不需要AI权...
透明软件!德州游戏辅助器大全,... 透明软件!德州游戏辅助器大全,wpk有透视挂吗,hhpoker的辅助是真的(有挂德州外挂)是一款可以...
七分钟ai智能!APPoker... 《hhpoker软件透明挂》是一款多人竞技的hhpoker辅助透视游戏,你将微扑克对手来到同一个战场...