Trapping Rain Water LT42 _Water

少年乘勇气，百战过乌孙。这篇文章主要讲述Trapping Rain Water LT42相关的知识，希望能为你提供帮助。

文章图片

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

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.
Brute force: for each element/bar, find the left boundary and right boundary, the level of the water trapped on this bar is Min(leftBoundary, rightBoundary) - height[i].
start from the bar, scan to the left to get the leftBoundary, scan to the right to get the rightBoundary
【Trapping Rain Water LT42】Time complexity: O(n2)
Space complexity: O(1)

class Solution { public int trap(int[] height) { int area = 0; for(int i = 0; i < height.length; ++i) {int leftBoundary = height[i]; for(int j = 0; j < i; ++j) { leftBoundary = Math.max(leftBoundary, height[j]); }int rightBoundary = height[i]; for(int j = i+1; j < height.length; ++j) { rightBoundary = Math.max(rightBoundary, height[j]); }area += Math.min(leftBoundary, rightBoundary) - height[i]; }return area; } }

1.a It is observed that the leftBoundary and rightBoundary has been recomputed multiple times, with dynamic programing, we could compute them once and store the result in the array.
leftBoundary[i]: maximum height starting from left and ending at i, leftBoundary[i] = Math.max(leftBoundary[i-1], height[i])
rightBoundary[j]: maximum height starting from right and ending at j, rightBoundary[j] = Math.max(rightBoundary[j+1], height[j])
Time Complexity: O(n)
Space Complexity: O(n)

public class SolutionLT42 { private int findMaxHeight(int[] height) { int result = 0; for(int i = 0; i < height.length; ++i) { if(height[i] > height[result]) { result = i; } } return result; } public int trap(int[] height) { if(height == null || height.length < = 1) return 0; int highestBar = findMaxHeight(height); int area = 0; int leftBoundary = 0; for(int i = 0; i < highestBar; ++i) { leftBoundary = Math.max(leftBoundary, height[i]); area += leftBoundary - height[i]; }int rightBoundary = 0; for(int i = height.length - 1; i > highestBar; --i) { rightBoundary = Math.max(rightBoundary, height[i]); area += rightBoundary - height[i]; }return area; }public static void main(String[] args) { SolutionLT42 subject = new SolutionLT42(); int[] testData = https://www.songbingjia.com/android/{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}; System.out.println(subject.trap(testData)); } }

1.4a Instead of doing two passes, we can start from the two ends to find out the boundary on the go with only 1 pass
if leftBounday < = rightBoundary, ++left, if height[left] < leftBoundary, area = leftBoundary - height[left]; otherwise leftBoundary = height[left]
else ++right, if height[right] < rightBoundary, area = rightBoundary - height[right]; otherwise rightBoundary = height[right]

public class SolutionLT42 {public int trap(int[] height) { if(height == null || height.length < = 1) return 0; int area = 0; int leftBoundary = height[0]; int rightBoundary = height[height.length - 1]; for(int left = 0, right = height.length - 1; left < right; ) { if(leftBoundary < = rightBoundary) { ++left; leftBoundary = Math.max(leftBoundary, height[left]); area += leftBoundary - height[left]; } else { --right; rightBoundary = Math.max(rightBoundary, height[right]); area += rightBoundary - height[right]; } } return area; }public static void main(String[] args) { SolutionLT42 subject = new SolutionLT42(); int[] testData = https://www.songbingjia.com/android/{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}; System.out.println(subject.trap(testData)); } }

2. Use stack, in order to store the boundary for a bar, we need to store the index of height in decreasing order of height, hence the previous element before the current would be the leftBoundary, if height[i] < = height[leftBoundaryStack.peek()], leftBoundaryStack.push(i); otherwise, the current element would be the rightBoundary.

public class SolutionLT42 {public int trap(int[] height) { if(height == null || height.length < = 1) return 0; int area = 0; Deque< Integer> leftBoundaryStack = new LinkedList< > (); for(int i = 0; i < height.length; ++i) { while(!leftBoundaryStack.isEmpty() & & height[leftBoundaryStack.peek()] < height[i]) { int rightBoundary = height[i]; int current = leftBoundaryStack.pop(); if(leftBoundaryStack.isEmpty()) { break; } int leftBoundary = height[leftBoundaryStack.peek()]; area += (Math.min(leftBoundary, rightBoundary) - height[current]) * (i - leftBoundaryStack.peek() - 1); } leftBoundaryStack.push(i); } return area; } }

Refactoring the above code, replace while loop with if, especially the ++i, interesting...

public class SolutionLT42 {public int trap(int[] height) { if(height == null || height.length < = 1) return 0; int area = 0; Deque< Integer> leftBoundaryStack = new LinkedList< > (); for(int i = 0; i < height.length; ) { if(leftBoundaryStack.isEmpty() || height[leftBoundaryStack.peek()] > height[i]) { leftBoundaryStack.push(i); ++i; } else { int current = leftBoundaryStack.pop(); if(leftBoundaryStack.isEmpty()) { continue; } int rightBoundary = height[i]; int leftBoundary = height[leftBoundaryStack.peek()]; int distance = i - leftBoundaryStack.peek() - 1; int boundedHeight = Math.min(leftBoundary, rightBoundary) - height[current]; area += distance * boundedHeight; } } return area; }}