目录
- 350-两个数组的交集
- 283-移动零
- 1-两数之和
- 25-K 个一组翻转链表
- 581-最短无序连续子数组
- 合并区间
- 螺旋矩阵
- 数组中相加和为0的三元组
- 数组中出现次数超过一半的数字
- 字符串出现次数的TopK问题
- 206-反转链表
- 160-相交链表
- 19-删除链表的倒数第N个节点
- 21-合并两个有序链表
- 31-下一个排列
- 链表K位翻转
- 链表排序-归并算法
- 判断链表中是否有环
- 设计LRU缓存结构
- 两个链表的第一个公共结点
- 两个链表生成相加链表
- 合并N个有序链表
- 链表内指定区间反转
接雨水问题
访问量:1401
一、简介
给定一个整形数组arr,已知其中所有的值都是非负的,将这个数组看作一个柱子高度图,计算按此排列的柱子,下雨之后能接多少雨水。(数组以外的区域高度视为0)
案例
输入: [3,1,2,5,2,4] 返回值: 5 说明: 数组 [3,1,2,5,2,4] 表示柱子高度图,在这种情况下,可以接 5个单位的雨水,蓝色的为雨水 ,如题面图。
二、实现
func maxWater(arr []int) int64{ if len(arr) <=2 { return 0 } // 确定左边节点 leftIndex := 0 for i:=1; i< len(arr); i++ { if arr[i] < arr[leftIndex] { break } leftIndex ++ } if leftIndex == len(arr) -1 { return 0 } // 确定 中间最低点 midIndex := leftIndex +1 for i:= leftIndex+2; i < len(arr); i++ { if arr[i] > arr[midIndex] { break } midIndex ++ } if midIndex == len(arr) -1 { return 0 } // 确定 右侧的最高点 rightIndex := midIndex +1 for i:= rightIndex+1; i< len(arr); i++ { if arr[rightIndex] > arr[leftIndex] { break } if arr[i] > arr[rightIndex] { rightIndex = i } } // 计算从leftIndex ~ rightIndex 直接可存储的水量 maxVal := 0 minNode := arr[leftIndex] if arr[leftIndex] < arr[rightIndex] { minNode = arr[leftIndex] } else{ minNode = arr[rightIndex] } // 去掉中间的节点 for i:= leftIndex+1; i< rightIndex; i++ { maxVal += minNode - arr[i] } if rightIndex == len(arr) -1 { return int64(maxVal) } return int64(maxVal) + maxWater(arr[rightIndex:]) }
题目来源:牛客
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助