`
bcyy
  • 浏览: 1881081 次
文章分类
社区版块
存档分类
最新评论

Trapping Rain Water -- LeetCode

 
阅读更多
原题链接:http://oj.leetcode.com/problems/trapping-rain-water/
这道题比较直接的做法类似Longest Palindromic Substring中的第一种方法,对于每一个bar往两边扫描,找到它能承受的最大水量,然后累加起来即可。每次往两边扫的复杂度是O(n),对于每个bar进行处理,所以复杂度是O(n^2),空间复杂度是O(1)。思路比较清晰,就不列代码了,有兴趣的朋友可以实现一下哈。

下面我们说说优化的算法。这种方法是基于动态规划的,基本思路就是维护一个长度为n的数组,进行两次扫描,一次从左往右,一次从右往左。第一次扫描的时候维护对于每一个bar左边最大的高度是多少,存入数组对应元素中,第二次扫描的时候维护右边最大的高度,并且比较将左边和右边小的最大高度(我们成为瓶颈)存入数组对应元素中。这样两遍扫描之后就可以得到每一个bar能承受的最大水量,从而累加得出结果。这个方法只需要两次扫描,所以时间复杂度是O(2*n)=O(n)。空间上需要一个长度为n的数组,复杂度是O(n)。代码如下:

public int trap(int[] A) {
    if(A==null || A.length==0)
        return 0;
    int max = 0;
    int res = 0;
    int[] container = new int[A.length];
    for(int i=0;i<A.length;i++)
    {
        container[i]=max;
        max = Math.max(max,A[i]);
    }
    max = 0;
    for(int i=A.length-1;i>=0;i--)
    {
        container[i] = Math.min(max,container[i]);
        max = Math.max(max,A[i]);
        res += container[i]-A[i]>0?container[i]-A[i]:0;
    }    
    return res;
}
这个方法算是一种常见的技巧,从两边各扫描一次得到我们需要维护的变量,通常适用于当前元素需要两边元素来决定的问题,非常类似的题目是Candy,有兴趣的朋友可以看看哈。

分享到:
评论

相关推荐

    C语言-leetcode题解之42-trapping-rain-water.c

    c语言入门 C语言_leetcode题解之42-trapping-rain-water.c

    js-leetcode题解之42-trapping-rain-water.js

    js js_leetcode题解之42-trapping-rain-water.js

    leetcode不会-3D-Trapping-Rain-Water-System:该repo包含复杂3D雨水收集系统的解决方案,该系统在Lee

    leetcode 不会3D 捕集雨水系统 该 repo 包含复杂 3D 雨水收集系统的解决方案,该系统在 Leetcode Problem No. 407 和 Google Interview Round 中提出。 此外,它将“0”视为系统的排水。 (查看自述文件以获得详细...

    javalruleetcode-LeetCode:LeetCode算法问题

    Trapping Rain Water LeetCode 61 RotateList LeetCode 75 Sort Colors LeetCode 125 Valid Palindrome LeetCode 167 Two Sum II - Input array is sorted LeetCode 344 Reverse String LeetCode 345 Reverse Vowels...

    多线程leetcode-leetcode-java:leetcode上的题解,基于java语言

    多线程 leetcode 前言 每天刷点leetcode,基于java语言实现。 leetcode上难度分三档:easy,medium,hard. 如下: easy medium Remove Nth Node From End of List Swap Nodes ...Trapping Rain Water

    leetcode-cpp刷题

    - **2.1.15 Trapping Rain Water** - 计算雨水能够困住的水量。 - 实现思路:使用动态规划方法,记录每条柱子左侧最高值和右侧最高值,然后计算水量。 - **2.1.16 Rotate Image** - 将一个正方形矩阵顺时针旋转...

    leetcode1004-leetcode:leetcode删号重练个人记录:)

    leetcode 1004 leetcode NEXT:42 Trapping Rain Water 刷题顺序 刷题内容总的来说包括数据结构、算法和技巧 按照tag分类别进行刷题,跳过like&lt;200&gt;like的题目 按Acceptance由高到低进行,每个tag所刷题目大于20...

    _leetcode-python.pdf

    - Trapping Rain Water: 给定一个数组,其中每个元素代表一个宽度为1的柱子高度,计算能接多少雨水。 - Multiply Strings: 给定两个非负整数字符串形式的数,要求进行乘法运算。 - Wildcard Matching: 实现支持'?'和...

    Leetcode-Solutions:JavaScript 语言的 Leetcode 解决方案

    力码解决方案 Leetcode是一个网站,人们——...├── Trapping Rain Water │ ├── Readme.md │ └── solution.js ├── Wildcard Matching │ ├── Readme.md │ └── solution.js ├── Valid Number │

    leetcode卡-LeetCode:我的LeetCode解决方案

    Trapping Rain Water II], BFS/Priority queue 2017.06.19 打卡[LeetCode 145. Binary Tree Postorder Traversal], Tree/stack 2017.06.20 打卡[LeetCode 107. Binary Tree Level Order Traversal II], Tree/BFS ...

    leetcode跳跃-leetcode:leetcode解题之路

    接雨水](./Array/trapping-rain-water.md) [0048 旋转图像](./Array/rotate-image.md) Heap 堆 [0023 合并K个排序链表](./Heap/merge-k-sorted-lists.md) String 字符串 [0006 Z字形变换](./String/zigzag-...

    python-leetcode面试题解之第42题接雨水-题解.zip

    在本压缩包中,我们关注的是一个Python编程相关的学习资源,特别针对LeetCode平台上的第42题“接雨水”(Trapping Rain Water)的面试题解。LeetCode是一个广泛被程序员用来提升算法技能和准备面试的在线平台,其中...

    lrucacheleetcode-leetcode:leetcode

    Trapping Rain Water 85. Maximal Rectangle Monotonic stack for 2d array 239. Sliding Window Maximum 255. Verify Preorder Sequence in Binary Search Tree 907. Sum of Subarray Minimums 二叉搜索树 99. ...

    C语言入门-leetcode练习之第42题接雨水.zip

    接下来,我们转向LeetCode的第42题“接雨水”(Trapping Rain Water)。这是一道典型的二维数组问题,考察的是动态规划和双指针技巧。 题目描述:给定一个高度不一的数组代表地面,雨水会积累在低点。求能容纳的...

    leetcode添加元素使和等于-leetcode:力码

    trapping-rain-water 滑动窗口 通过窗口的大小不断调整来找到合适的值,或者窗口大小不变,通过左右移动来找到相应的结果 \ \ 其他 非 LeetCode 题,单纯在别人面试中看到的 \ 链表 \ swap-nodes-in-pairs linked-...

    LeetCode最全代码

    # [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...

    leetcode添加元素使和等于-leetcode:我的leetcode解决方案

    leetcode添加元素使和等于 经验教训 一定要吧功能尽量细化为函数,这样一者做题思路比较清晰,二者可以在某些情况下直接return值。 如果输入的形式是一个序列,则可以想想:分治、动规、贪婪,一般不建议搜索,因为...

    leetcode答案-leetcode:leetcode.com问题的答案

    leetcode 答案leetcode leetcode.com 问题的答案 跑步 python -m venv .venv source .venv/bin/activate pip install -r requirements.txt pytest &lt;question&gt;/tests.py ...lc42_trapping_rain_water/tests.py

    收集面试中提出的一些重要问题。-C/C++开发

    收集面试中提出的一些重要问题。 数据结构算法面试问题面试中提出的一些重要问题的集合。...数组https://leetcode.com/problems/3sum/ [解决方案] https://leetcode.com/problems/trapping-rain-water/ [解决方案] ...

    erlang入门级练习:LeetCode OJ问题的部分erlang 源码

    我自己在新学erlang,在LeetCode OJ上找了题目练习,题目很适合新手... "three_sum.erl","trapping_rain_water.erl", "valid_palindrome.erl" 个人认为dungeon_game这个题目解题逻辑很体现erlang的函数式的思维逻辑

Global site tag (gtag.js) - Google Analytics