网站制作客户资料,小型公司网络搭建,管理员网站,重庆建筑施工信息网接雨水 文章目录 接雨水1 题目描述2 分析2.1 左到右2.2 右到左2.3 计算面积 3 代码3.1 Java3.2 Python 附录1 1 题目描述
https://leetcode.cn/problems/trapping-rain-water/
面试的时候关键不是你的手法多么精妙#xff0c;首先要做出来。 给定 n 个非负整数表示每个宽度为…接雨水 文章目录 接雨水1 题目描述2 分析2.1 左到右2.2 右到左2.3 计算面积 3 代码3.1 Java3.2 Python 附录1 1 题目描述
https://leetcode.cn/problems/trapping-rain-water/
面试的时候关键不是你的手法多么精妙首先要做出来。 给定 n 个非负整数表示每个宽度为 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 个单位的雨水蓝色部分表示雨水。 输入height [4,2,0,3,2,5] 输出9 2 分析
通过观察我们知道要计算接的水我们要找到能够存水的凹槽 我们将这些存水的凹槽的边缘连接起来可以发现折线图的总体趋势是从低到高从高到低下图是随机生成的不同高度下的存水凹槽边缘图以及其连线 绘图代码已经在附录1中给出可以直接运行随机生成数据以及查看绘图。 那么我们能做的就是从左到右依次找到越来越高的值保存其索引从右到左依次找到越来越高的值保存其索引。然后计算这些索引之间的最大盛水面积减去之间的柱子的面积就是最后的接雨水的结果。
2.1 左到右
while start len(height) and height[start] 0: # 指针不断右移跳过为0的元素start start 1
if start len(height) - 1: # 要是全为0return 0return 0
lists.append(height[start]) # 保存值
indexes.append(start) # 保存索引
for i in range(start 1, len(height)):if height[i] lists[-1]: # 比上一个凹槽边缘大或者等于保存lists.append(height[i])indexes.append(i)2.2 右到左
# 注意从右到左不要超过左到右的边界indexes[-1]while end indexes[-1] and height[end] 0: end end - 1
# 而且从左到右已经判断完全0了接下来不用判断了
reverse_lists.append(height[end])
reverse_indexes.append(end)
for i in range(end - 1, indexes[-1] - 1, -1): # 从右到左注意边界
# 注意range(end - 1, indexes[-1] - 1, -1)举个例子如果要生成一个10~0的
# 序列则为range(10, -1, -1)我们知道range的前两个参数为范围前闭后开[10,-1)
# 第二个-1为step表示按照反向遍历。if height[i] reverse_lists[-1]:reverse_lists.append(height[i])reverse_indexes.append(i)2.3 计算面积
最直接的想法是直接分开计算面积
l_res 0
for i in range(1, len(lists)):l indexes[i - 1]r indexes[i]l_res l_res (r - l - 1) * (min(height[l], height[r])) # 高度最小值乘以长度# 长度为right - left - 1for j in range(l 1, r):l_res l_res - height[j] # 减去中间的面积for i in range(len(reverse_indexes) - 2, -1, -1): # 反过来遍历r reverse_indexes[i]l reverse_indexes[i 1]l_res l_res (r - l - 1) * (min(height[l], height[r]))for j in range(l 1, r):l_res l_res - height[j]
return l_res
为了简单计算首先我们将两个索引合并
l_res 0
# 将indexes和reversed(reverse_indexes)合并
indexes.extend(reversed(reverse_indexes))在上面的图中我们看到两边的索引左到右[0, 3, 5]右到左[19, 16, 11, 7, 5]有重叠合并以后变成了[0, 3, 5, 5, 7, 11, 16, 19]怎么办
无所谓重叠之后长度为0二者之间的面积还是0不会对最终的面积有啥影响。
那么最后计算面积的过程为
for i in range(1, len(indexes)):l indexes[i - 1]r indexes[i]l_res l_res max((r - l - 1), 0) * (min(height[l], height[r]))for j in range(l 1, r):l_res l_res - height[j]
return l_res3 代码
3.1 Java
class Solution {public int trap(int[] height) {if (height.length 1) return 0;ListInteger lists new ArrayList();ListInteger indexes new ArrayList();ListInteger reverse_lists new ArrayList();ListInteger reverse_indexes new ArrayList();int start 0;int end height.length - 1;while(start height.length height[start] 0) start;if (start height.length - 1) return 0;lists.add(height[start]);indexes.add(start);for (int i start 1; i height.length; i) {if (height[i] lists.get(lists.size() - 1)) {lists.add(height[i]);indexes.add(i);}}int l_res 0;for (int i 1; i lists.size(); i) {int l indexes.get(i - 1);int r indexes.get(i);l_res (r - l - 1) * (Math.min(height[l], height[r]));for (int j l 1; j r; j) {l_res - height[j];}}while(end indexes.get(indexes.size() - 1) height[end] 0) end--;reverse_lists.add(height[end]);reverse_indexes.add(end);for (int i end - 1; i indexes.get(indexes.size() - 1); i--) {if (height[i] reverse_lists.get(reverse_lists.size() - 1)) {reverse_lists.add(height[i]);reverse_indexes.add(i);}}for (int i reverse_indexes.size() - 2; i 0; i--) {int r reverse_indexes.get(i);int l reverse_indexes.get(i 1);l_res (r - l - 1) * (Math.min(height[l], height[r]));for (int j l 1; j r; j) {l_res - height[j];}}return l_res;}
}3.2 Python
class Solution(object):# python 代码def trap(self, height)::type height: List[int]:rtype: intif len(height) 1:return 0lists []indexes []reverse_lists []reverse_indexes []start 0end len(height) - 1while start len(height) and height[start] 0:start start 1if start len(height) - 1:return 0lists.append(height[start])indexes.append(start)for i in range(start 1, len(height)):if height[i] lists[-1]:lists.append(height[i])indexes.append(i)while end indexes[-1] and height[end] 0:end end - 1reverse_lists.append(height[end])reverse_indexes.append(end)for i in range(end - 1, indexes[-1] - 1, -1):if height[i] reverse_lists[-1]:reverse_lists.append(height[i])reverse_indexes.append(i)l_res 0# 将indexes和reversed(reverse_indexes)合并indexes.extend(reversed(reverse_indexes))for i in range(1, len(indexes)):l indexes[i - 1]r indexes[i]l_res l_res max((r - l - 1), 0) * (min(height[l], height[r]))for j in range(l 1, r):l_res l_res - height[j]return l_res附录1
# python 代码
def trap(height)::type height: List[int]:rtype: intif len(height) 1:return 0lists []indexes []reverse_lists []reverse_indexes []start 0end len(height) - 1while start len(height) and height[start] 0:start start 1if start len(height) - 1:return 0lists.append(height[start])indexes.append(start)for i in range(start 1, len(height)):if height[i] lists[-1]:lists.append(height[i])indexes.append(i)while end indexes[-1] and height[end] 0:end end - 1reverse_lists.append(height[end])reverse_indexes.append(end)for i in range(end - 1, indexes[-1] - 1, -1):if height[i] reverse_lists[-1]:reverse_lists.append(height[i])reverse_indexes.append(i)l_res 0# 将indexes和reversed(reverse_indexes)合并history_indexes indexes.copy()indexes.extend(reversed(reverse_indexes))for i in range(1, len(indexes)):l indexes[i - 1]r indexes[i]l_res l_res max((r - l - 1), 0) * (min(height[l], height[r]))for j in range(l 1, r):l_res l_res - height[j]return l_res, history_indexes, reverse_indexesdef draw_pic(water, indexes, reverse_indexes):indexes.extend(reverse_indexes)indexes list(set(indexes))indexes.sort()# 绘制折线图x轴为indexesy轴为water[indexes]plt.plot(indexes, [water[i] for i in indexes])plt.scatter(indexes, [water[i] for i in indexes])# 将water绘制成柱状图plt.bar(range(len(water)), water, coloryellow, zorder1, edgecolorblack, linewidth1)# 将indexes绘制成柱状图绿色plt.bar(indexes, [water[i] for i in indexes], colorg, zorder100, edgecolorblack, linewidth1)# 设置 x 轴刻度及标签plt.xticks(np.arange(0, 20), range(0, 20))plt.show()# 生成一个更长的测试用例
import random
random.randint(0, 10)
water [random.randint(0, 10) for _ in range(20)]res trap(water)
indexes res[1]
reverse_indexes res[2]
draw_pic(water, indexes, reverse_indexes)
