Skip to content

Latest commit

 

History

History
75 lines (53 loc) · 1.73 KB

0042-trapping-rain-water.adoc

File metadata and controls

75 lines (53 loc) · 1.73 KB

42. Trapping Rain Water

{leetcode}/problems/trapping-rain-water/[LeetCode - 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.

Example:

{image_attr}

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!

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

解题分析

{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
一刷
link:{sourcedir}/_0042_TrappingRainWater.java[role=include]
二刷
link:{sourcedir}/_0042_TrappingRainWater_2.java[role=include]
三刷
link:{sourcedir}/_0042_TrappingRainWater_3.java[role=include]

思考题

尝试一下动态规划解法！