C/C++教程

[Leetcode 42]雨天积水面积Trapping Rain Water

本文主要是介绍[Leetcode 42]雨天积水面积Trapping Rain Water,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目

下雨天的蓄水量计算

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

 

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

 

思路

最初简单的以为是leetcode11变式,left和right指针总最大面积-中间height

但其实有很多不同,比如中间height值特别大,比如不止一个left right

 

所以,要找到最大的height[max],将其分成[0,max] [max,len]讨论

在俩区间中,分别讨论除了max,较大的height[larger],对每个height[i],用height[larger]-height[i]得到当前点的蓄水量

 

代码

 

 

    public static int trap(int[] height) {

        int area=0;
        int maxindex=0;
        for(int i=0;i<height.length;i++){
            if(height[maxindex]<height[i])
                maxindex=i;
        }
        int leftBar=0;
        for(int i=0;i<maxindex;i++){
            if(height[i]>leftBar){
                leftBar=height[i];//更新挡板,更高,无法蓄水
            }
            else{
                area+=leftBar-height[i];//比挡板矮,蓄水
            }
        }

        int rightBar=0;
        for(int i=height.length-1;i>maxindex;i--){
            if(height[i]>rightBar){
                rightBar=height[i];//挡板
            }
            else {
                area+=rightBar-height[i];//比挡板矮,蓄水
            }
        }
        return area;
    }

 

这篇关于[Leetcode 42]雨天积水面积Trapping Rain Water的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!