- 浏览: 173236 次
- 性别:
- 来自: 济南
文章分类
最新评论
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.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map 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. Thanks Marcos for contributing this image!
让我们计算出存水的总量,如果从左边依次计算,计算当前最高点和最低点之间的存水量,这样计算的结果小于实际的存水量,因为当前的最底点可能会被淹没(如果它两边有比它高的,它就会被淹没)。我们可以采用两个指针,从两边开始,找到一个最高点,然后再找到一个次高点,保持最高点不动,只移动次高点,次高点减去移动经过的柱子就是总的存水量。代码如下:
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map 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. Thanks Marcos for contributing this image!
让我们计算出存水的总量,如果从左边依次计算,计算当前最高点和最低点之间的存水量,这样计算的结果小于实际的存水量,因为当前的最底点可能会被淹没(如果它两边有比它高的,它就会被淹没)。我们可以采用两个指针,从两边开始,找到一个最高点,然后再找到一个次高点,保持最高点不动,只移动次高点,次高点减去移动经过的柱子就是总的存水量。代码如下:
public class Solution { public int trap(int[] height) { if(height == null || height.length < 3) return 0; int left = 0; int right = height.length - 1; int secondMaxHeight = Integer.MIN_VALUE; int area = 0; while(left < right) { if(height[left] < height[right]) { secondMaxHeight = Math.max(secondMaxHeight, height[left]); area += secondMaxHeight - height[left]; left ++; } else { secondMaxHeight = Math.max(secondMaxHeight, height[right]); area += secondMaxHeight - height[right]; right --; } } return area; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 225Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 223You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 340Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 331Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 449Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 509Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 428Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 426The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 385Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 515Given a matrix of m x n element ... -
Repeated DNA Sequences
2016-03-03 03:10 367All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 859Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 880Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 553Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 599Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 762Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 732You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 627For a undirected graph with tre ... -
Bulb Switcher
2016-02-28 12:12 347There are n bulbs that are init ...
相关推荐
Trapping Rain Water 刷题顺序 刷题内容总的来说包括数据结构、算法和技巧 按照tag分类别进行刷题,跳过like<200>like的题目 按Acceptance由高到低进行,每个tag所刷题目大于20(对于类型较少的题目大于5),则进入下...
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...
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. ...
Trapping Rain Water Rotate Image Plus One Climbing Stairs Set Matrix Zeroes Gas Station Candy Majority Element Rotate Array Contains Duplicate Contains Duplicate II Contains Duplicate III Product of ...
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是一个网站,人们——...├── Trapping Rain Water │ ├── Readme.md │ └── solution.js ├── Wildcard Matching │ ├── Readme.md │ └── solution.js ├── Valid Number │
Trapping Rain Water Integer to English Words Regular Expression Matching Merge K Sorted Lists Remove Invalid Parentheses Serialize and Deserialize Binary Tree Minimum Window Substring C++ STL中常见...
...The number of questions is increasing recently. Here is the classification of all `468` questions. ...I'll keep updating for full summary and better solutions....|-----|---------------- | --------------- |...
二、trapping rain water 雨水收集问题 问题描述 给定一个 number 组成的数组,值代表箱子的高度,下雨后,这些箱子中的间隙一共能收集到多少雨水 解答 暴力破解: 遍历数组,找当前 index 往左的最大值和当前 index...
多线程 leetcode 前言 每天刷点leetcode,基于java语言实现。 leetcode上难度分三档:easy,medium,hard. 如下: easy medium Remove Nth Node From End of List Swap Nodes ...Trapping Rain Water
leetcode 不会3D 捕集雨水系统 该 repo 包含复杂 3D 雨水收集系统的解决方案,该系统在 Leetcode Problem ...您必须编写一个函数来计算如果我们将无限供应的水倒在该建筑上时将存储在该建筑中的水量。...
我自己在新学erlang,在LeetCode OJ上找了题目练习,题目很适合新手... "three_sum.erl","trapping_rain_water.erl", "valid_palindrome.erl" 个人认为dungeon_game这个题目解题逻辑很体现erlang的函数式的思维逻辑
收集面试中提出的一些重要问题。 数据结构算法面试问题面试中提出的一些重要问题的集合。...数组https://leetcode.com/problems/3sum/ [解决方案] https://leetcode.com/problems/trapping-rain-water/ [解决方案] ...
作业说明 代码注释中有力扣链接. 第一周作业 循环队列, 双向循环队列, 双向队列, 双向链表, 链表, 爬楼梯, 盛最多水的容器, 柱状图中最大的矩形, ...删除有序数组中的重复项, ...接雨水, trapping-rain-water.ts 两数之和,
接雨水](./Array/trapping-rain-water.md) [0048 旋转图像](./Array/rotate-image.md) Heap 堆 [0023 合并K个排序链表](./Heap/merge-k-sorted-lists.md) String 字符串 [0006 Z字形变换](./String/zigzag-...
leetcode 答案leetcode leetcode.com 问题的答案 跑步 python -m venv .venv source .venv/bin/activate pip install -r requirements.txt pytest <question>/tests.py ...lc42_trapping_rain_water/tests.py
trapping-rain-water 滑动窗口 通过窗口的大小不断调整来找到合适的值,或者窗口大小不变,通过左右移动来找到相应的结果 \ \ 其他 非 LeetCode 题,单纯在别人面试中看到的 \ 链表 \ swap-nodes-in-pairs linked-...