42. Trapping Rain Water (Hard)
https://leetcode.com/problems/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.
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
Solutions
class Solution {
// Sort out all the peaks, then merge the peaks if possible.
public int trap(int[] height) {
int ans = 0;
if (height == null || height.length <= 2) {
return 0;
}
int len = height.length;
List<Integer> peaks = new ArrayList<>();
for (int i = 0; i < len; i++) {
if (i == 0) {
if (height[0] > height[1]) {
peaks.add(0);
}
continue;
}
if (i == len - 1) {
if (height[len - 1] > height[len - 2]) {
peaks.add(len - 1);
}
continue;
}
if (height[i] >= height[i - 1] && height[i] >= height[i + 1]) {
peaks.add(i);
}
}
// the first and last peak should be processed properly. They can merge neighboring
// peaks if possible rather than merged by others.
while (peaks.size() > 2) {
List<Integer> toRemove = new ArrayList<>();
for (int i = 1; i < peaks.size() - 1; i ++) {
int left = height[peaks.get(i - 1)];
int mid = height[peaks.get(i)];
int right = height[peaks.get(i + 1)];
// peak[i-1] >= peak[i] <= peak[i+1], then peak[i] is merged
if (mid <= left && mid <= right) {
toRemove.add(peaks.get(i));
}
}
if (toRemove.size() == 0) {
break;
}
peaks.removeAll(toRemove);
}
for (int i = 0; i < peaks.size() - 1; i++) {
int minH = Math.min(height[peaks.get(i)], height[peaks.get(i + 1)]);
for (int j = peaks.get(i) + 1; j <= peaks.get(i + 1) - 1; j++) {
// FIXME height[j] may be larger than minnH
ans += minH <= height[j] ? 0 : minH - height[j];
}
}
return ans;
}
}
Incorrect Solutions
class Solution {
// Incorrect Solution
// Larger container can cover the inner small containers.
// This problem is relatively easy. The major point is sort all the peak1->valley-peak2 patterns
// which can hold water and when rain drops. The volume of the water it traps is determined by the
// relative lower peak.
public int trap(int[] height) {
int ans = 0;
if (height == null || height.length <= 2) {
return 0;
}
int len = height.length;
int peak1 = -1;
int peak2 = -1;
int valley = -1;
for (int i = 0; i < len; i++) {
// if it is the first element
if (i == 0) {
// set the first peak1
if (height[0] > height[1]) {
peak1 = 0;
}
// ignore it if 0 is a valley
}
// if the last element
else if (i == len - 1) {
// set the last peak2
if (height[len - 1] > height[len - 2]) {
peak2 = len - 1;
}
// ignore it if len-1 is a valley
}
// lower than both sides
else if (height[i] < height[i - 1] && height[i] < height[i + 1]) {
// the left peak must be already determined
valley = i;
}
// higher than both sides
else if (height[i] > height[i - 1] && height[i] > height[i + 1]) {
// valley not find yet, set peak1 first
if (valley < 0) {
peak1 = i;
}
// valley already set, set it to peak2
else {
peak2 = i;
}
}
// calculate the volume of the container if it is formed.
if (peak1 >= 0 && peak2 >= 0 && valley >= 0) {
int minH = Math.min(height[peak1], height[peak2]);
for (int j = peak1; j <= peak2; j++) {
ans += height[j] >= minH ? 0 : minH - height[j];
}
// after calculation, reset the peaks and valleys
valley = -1;
// right peak peak2 can be the next water container's left peak
peak1 = peak2;
peak2 = -1;
}
}
return ans;
}
}