数组接雨水

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

上面是由数组 [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

哈哈哈, 不少人第一眼看到这个都是懵的, 好像完全没有学过的知识点可以指出思路. 好在计算机就是计算能力强, 用暴力法处理试试.

按照题目要求, 一个位置i能积水, 那么左边肯定有比height[i]大的值, 右边肯定也得有比height[i]大的值, 找到左右2边比height[i]大的值, 然后取出较小值-height[i] 就是位置i上能积的水分.

由于有2层循环, 所以需要O(n^2)的时间复杂度, 不出意外, 果然没有通过性能测试.

class Solution {func trap(_ height: [Int]) -> Int {var result = 0for (i,_) in height.enumerated() {result += getIndex(height, index: i)}return result}/// 暴力法, 计算出index下的积水深度func getIndex(_ height: [Int], index: Int) -> Int {if index==0 || index == height.count-1 {return 0}// 比较的基准值,大于基准值才可能有积水let target = height[index]// index从左右各自找出最大值,然后min(height[leftMax],height[rightMax])-height[index]就是能积的水份var leftMax = indexvar rightMax = indexfor (i,item) in height.enumerated() {// 只有>height[index]才可能有积水if item<=target {continue}// 找到左边的最大值if iheight[leftMax] {leftMax = i}// 找到右边的最大值if i>index && item>height[rightMax] {rightMax = i}}// 左右都有大于的值,才可以积水,有一个不满足,那就是不能积水if leftMax == index || rightMax == index {return 0}// 可以积水的深度为 min(height[leftMax], height[rightMax]) - targetlet result = min(height[leftMax], height[rightMax]) - targetprint("\(index)可以积水,左边为\(leftMax),右边为\(rightMax),积水为\(result)")return result}}

下面开始介绍优化版, 上面的时间复杂度都用在了查找第i个元素的左右最大值上了, 这个是一个可以优化的点,

第i个元素左侧的最大值, 这个是不需要遍历的, 用一个变量leftMax, 在从[0,i]遍历的过程中维护好这个leftMax即可;
右侧的最大值, 可以先遍历一遍数组,找到整个数组的最大值maxHeight;
然后用整个数组的最大值把数组分割成2组, 一组是从[0,maxHeight], 一组是[maxHeight, 数组.count-1]; 
在第一个数组[0,maxHeight], 第i个元素的左侧最大值就是leftMax, 右侧最大值就是maxHeight, 这样可以计算出[0,maxHeight]之间可以积攒的雨水之和;
在第二个数组中, 采用倒序遍历的过程, [maxHeight, 数组.count-1]中的第i个元素, 左侧最大值是maxHeight, 右侧最大值用维护好的一个变量rightMax, 这样就计算出[maxHeight, 数组.count-1]之间的积累的雨水了;
至于maxHeight这个, 由于是最大值了, 左右都不会有大于maxHeight的值, 肯定是不会有雨水的.

到此, 思路就说完了, 有个图会更好理解. 这个算法已经不错了, 只需要2次循环, 在O(n)时间内解决.

在思考的过程中考虑了很多种情况,
比如说最大值出现在起始位置或者结束位置, 这样的话, 起始是没有影响的, 只不过数组分割成2份的时候一组是空值而已.
还有比如说最大值是重复的, 有2个或者2个以上的最大值, 但是这样对于分割也是没有影响的, 而且完全不需要改动就能适应这种情况

class Solution {func trap(_ height: [Int]) -> Int {var maxHeight = (0,0)// 通过遍历找到最大值和对应的下标for (i,item) in height.enumerated() {if item>=maxHeight.1 {maxHeight = (i,item)}}var result = 0var leftMax = (0,0)// 然后从[0,最大值]计算最大值左侧的结果for i in 0..leftMax.1 {leftMax = (i,item)}// 如果当前元素rightMax.1 {rightMax = (i,item)}// 如果当前元素

class Solution {func trap(_ height: [Int]) -> Int {if height.count <= 1 {return 0}var result = 0// 左右指针向中间最大值靠拢var left = 0var right = height.count-1var leftMax = height[0]var rightMax = height[height.count-1]while leftleftMax {leftMax = leftValue}result += leftMax-leftValueleft += 1continue}// 到这里说明,左边高,右边低,或者左右高度相等,if rightValue>rightMax {rightMax = rightValue}result += rightMax-rightValueright -= 1}return result}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！