文档章节

Trapping Rain Water 存水问题

大山_
 大山_
发布于 2016/07/25 18:32
字数 174
阅读 21
收藏 0

输入图片说明

上图索引位置值对应 数组 [0,1,0,2,1,0,1,3,2,1,2,1] 求上图蓝色方格(水滴)数量

public class Solution {
    public  int trap(int[] height) {
    	if (height == null || height.length<3){
    		 return 0;
    	}
    	
    	int max = 0;
    	int maxIndex = 0;
    	for(int i=0;i<height.length;i++){       //找到最大值及其数组索引
    		if (height[i]>max){
    			max = height[i];
    			maxIndex = i;
    		}
    	}           
    	
    	int leftMax = 0;
    	int result = 0;
        for (int i=0;i<maxIndex;i++){
            if (height[i]>=leftMax){
                leftMax = height[i];
            }else{
               result +=  (leftMax-height[i]);  //index索引上的存水量等于 左侧最大值-当前索引位置的值
            }
        }
        int rightMax = 0;
        for (int i=height.length-1;i>maxIndex;i--){
            if (height[i]>=rightMax){
                rightMax = height[i];
            }else{
               result +=  (rightMax-height[i]); //index索引上的存水量等于 右侧最大值-当前索引位置的值
            }
        }
        return result;
    }
}

© 著作权归作者所有

大山_
粉丝 6
博文 19
码字总数 6609
作品 0
石景山
私信 提问
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 is able to trap after raining. 把题意简化到左右高已知,中......

ShutLove
2018/05/28
0
0
水壶问题(向水壶中倒z升水) Water and Jug Problem

问题: You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exac......

叶枫啦啦
2017/12/27
0
0
福克纳《喧哗与骚动》:昆丁的自杀

这几天,我在重看《喧哗与骚动》(Sound and Fury)中昆丁自杀的那一章。 几年前,我第一次看的时候,很喜欢这一章。但是这一次看,我觉得写得过于冗芜了。 我现在有点好奇,不知道福克纳写的...

阮一峰
2006/08/11
0
0
水槽中倒水,Pour Water

问题: We are given an elevation map, representing the height of the terrain at that index. The width at each index is 1. After units of water fall at index , how much water is ......

叶枫啦啦
2018/02/01
0
0
超过 30 个你应该看看的 HTML5 体验

HTML5 是现在开发者谈论最多的话题之一,本文列举了超过 30 个使用 HTML5 Canvas 的体验,你值得一看。 FlowerPower Google gravity HTML5 logo Sketch webGL water fish waterfall Conducto...

红薯
2011/09/21
5.9K
9

没有更多内容

加载失败,请刷新页面

加载更多

利用mybatis generator生成实体类、Mapper接口以及对应的XML文件

项目中通常会遇到数据的持久化,如果是采用mybatis的orm,就会涉及到生成xml的问题,刚好mybatis官网提供了这么个插件MyBatis Generator,效果简直是棒呆。 1. 首先需要在build.gradle文件中...

啊哈关关
今天
2
0
SpringSocial相关的知识点

使用SprigSocial开发第三方登录 核心类 ServiceProvider(AbstractOauth2ServiceProvider):主要负责实现server提供商(例如QQ,微信等共有的东西),默认实现类是AbstractOauth2ServiceProvider...

chendom
今天
2
0
Java并发之AQS详解

一、概述   谈到并发,不得不谈ReentrantLock;而谈到ReentrantLock,不得不谈AbstractQueuedSynchronizer(AQS)!   类如其名,抽象的队列式的同步器,AQS定义了一套多线程访问共享资源...

群星纪元
昨天
2
0
Fabric-sdk-java最新教程

Fabric Java SDK是Fabric区块链官方提供的用于Java应用开发的SDK,全称为Fabric-sdk-java,网上可用资料不多,本文列出了精心整理的针对Fabric Java SDK的最新精选教程。 如果希望快速掌握F...

汇智网教程
昨天
3
0
react 子组件监听props 变化

componentWillReceiveProps //已经被废弃 getDerivedStateFromProps// 推荐使用//如果条件不存在必须要返回null static getDerivedStateFromProps(props, current_stat...

一箭落旄头
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部