Given an array of non-negative integers representing terraces in an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
Example #1
Input: arr[] = [2, 0, 2]
Output: 2
Structure is like below:
| |
|_|
We can trap 2 units of water in the middle gap.
Example #2
Input: arr[] = [3, 0, 0, 2, 0, 4]
Output: 10
Structure is like below:
|
| |
| | |
|__|_|
We can trap "3*2 units" of water between 3 an 2,
"1 unit" on top of bar 2 and "3 units" between 2
and 4. See below diagram also.
Example #3
Input: arr[] = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Output: 6 Structure is like below: | | || | _|_||_|||||| Trap "1 unit" between first 1 and 2, "4 units" between first 2 and 3 and "1 unit" between second last 1 and last 2.
思路：
用动态规划，遍历两遍数组，求左右的最大值，然后再遍历一遍数组取交集。
left_max.right_max.height array and update answer:
min(max_left[i], max_right[i]) − height[i] to answer.
示意图如下：
The concept is illustrated as shown:
代码如下：
/** * DYNAMIC PROGRAMMING approach of solving Trapping Rain Water problem. * * @param {number[]} terraces * @return {number} */ export default function dpRainTerraces(terraces) { let waterAmount = 0; // Init arrays that will keep the list of left and right maximum levels for specific positions. const leftMaxLevels = new Array(terraces.length).fill(0); const rightMaxLevels = new Array(terraces.length).fill(0); // Calculate the highest terrace level from the LEFT relative to the current terrace. [leftMaxLevels[0]] = terraces; for (let terraceIndex = 1; terraceIndex < terraces.length; terraceIndex += 1) { leftMaxLevels[terraceIndex] = Math.max( terraces[terraceIndex], leftMaxLevels[terraceIndex - 1], ); } // Calculate the highest terrace level from the RIGHT relative to the current terrace. rightMaxLevels[terraces.length - 1] = terraces[terraces.length - 1]; for (let terraceIndex = terraces.length - 2; terraceIndex >= 0; terraceIndex -= 1) { rightMaxLevels[terraceIndex] = Math.max( terraces[terraceIndex], rightMaxLevels[terraceIndex + 1], ); } // Not let‘s go through all terraces one by one and calculate how much water // each terrace may accumulate based on previously calculated values. for (let terraceIndex = 0; terraceIndex < terraces.length; terraceIndex += 1) { // Pick the lowest from the left/right highest terraces. const currentTerraceBoundary = Math.min( leftMaxLevels[terraceIndex], rightMaxLevels[terraceIndex], ); if (currentTerraceBoundary > terraces[terraceIndex]) { waterAmount += currentTerraceBoundary - terraces[terraceIndex]; } } return waterAmount; }
原文：https://www.cnblogs.com/Archer-Fang/p/10536110.html
