# Question

Formatted question description: https://leetcode.ca/all/42.html

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.

@tag-array


# Algorithm

Based on Dynamic Programming, maintaining a one-dimensional dp array, this DP algorithm needs to traverse the array two passes.

The first pass stores the maximum value of the left position of i in dp[i], and then starts the second pass to traverse the array.

In the second traversal, find the maximum value on the right, and then compare it with the maximum on the left to take the smaller value, and compare it with the current value A[i]. If it is greater than the current value, store the difference in the result.

Java

# Algorithm 2 - not finding the max height

If height has length 0, then return 0.

Loop over height in both directions and use two arrays leftMax and rightMax to store maximum height in both directions. Each element in the array leftMax represents the maximum height in the subarray from the leftmost index to the current index. Each element in the array rightMax represents the maximum height in the subarray from the current index to the rightmost index.

For each index i, the maximum amount of water trapped at the index is Math.min(leftMax[i], rightMax[i]) - height[i]. Thus the total amount of water trapped can be obtained.

class Solution_notFindingMaxHeight {
public int trap(int[] height) {
if (height == null || height.length == 0)
return 0;
int length = height.length;
int[] leftMax = new int[length]; // leftMax represents the maximum height in the subarray from the leftmost index to the current index
int[] rightMax = new int[length]; // rightMax represents the maximum height in the subarray from the current index to the rightmost index
leftMax[0] = height[0];
for (int i = 1; i < length; i++)
leftMax[i] = Math.max(height[i], leftMax[i - 1]);
rightMax[length - 1] = height[length - 1];
for (int i = length - 2; i >= 0; i--)
rightMax[i] = Math.max(height[i], rightMax[i + 1]);
int amount = 0;
for (int i = 0; i < length; i++)
amount += Math.min(leftMax[i], rightMax[i]) - height[i];
return amount;
}
}