README
¶
Trapping Rain Water
栈
在遍历数组时维护一个栈，将小于或等于栈顶的条形块的索引压入栈顶，栈从顶到底是由小变大的。当前条形块和栈顶条形块和栈顶前一个条形块组成积水区域。积水区域的面积等于 (min(current, stack.pre) - stack.top) * distance。
双指针
如果右边有更高的条形块，积水高度依赖于左侧最高的条形块，左边的指针往右走。如果左边有更高的条形块，积水高度依赖于右侧最高的条形块，右边的指针往左走。所以如果右边指针比左边指针高，左边的最高肯定低于右边最高，反之同理。
Documentation
¶
Overview ¶
* @lc app=leetcode id=42 lang=golang * * [42] Trapping Rain Water * * https://leetcode.com/problems/trapping-rain-water/description/ * * algorithms * Hard (46.72%) * Likes: 5869 * Dislikes: 107 * Total Accepted: 445.4K * Total Submissions: 945.9K * Testcase Example: '[0,1,0,2,1,0,1,3,2,1,2,1]' * * 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. * * * 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! * * Example: * * * Input: [0,1,0,2,1,0,1,3,2,1,2,1] * Output: 6 *
Source Files