trapping-rain-water

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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

&nbsp;
Example 1:
<img src="https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png" style="width: 412px; height: 161px;" />
<pre>
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.
</pre>

Example 2:

<pre>
Input: height = [4,2,0,3,2,5]
Output: 9
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == height.length</code></li>
	<li><code>1 &lt;= n &lt;= 2 * 104</code></li>
	<li><code>0 &lt;= height[i] &lt;= 105</code></li>
</ul>

trap

Trapping Rain Water

Container With Most Water

container-with-most-water

盛最多水的容器

Product of Array Except Self

product-of-array-except-self

除自身以外数组的乘积

Trapping Rain Water II

trapping-rain-water-ii

接雨水 II

Pour Water

pour-water

倒水

Maximum Value of an Ordered Triplet II

maximum-value-of-an-ordered-triplet-ii

有序三元组中的最大值 II

Stack

Array

Two Pointers

Dynamic Programming

Monotonic Stack

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

&nbsp;

示例 1：

<img src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/10/22/rainwatertrap.png" style="height: 161px; width: 412px;" />

<pre>
输入：height = [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 个单位的雨水（蓝色部分表示雨水）。 
</pre>

示例 2：

<pre>
输入：height = [4,2,0,3,2,5]
输出：9
</pre>

&nbsp;

提示：

<ul>
	<li><code>n == height.length</code></li>
	<li><code>1 &lt;= n &lt;= 2 * 104</code></li>
	<li><code>0 &lt;= height[i] &lt;= 105</code></li>
</ul>