This is the fourth day of my participation in Gwen Challenge
This article is participating in “Java Theme Month – Java Development in Action”, see the activity link for details
I am Chen PI, an ITer of Internet Coding. I search “Chen PI’s JavaLib” on wechat and read the latest articles as soon as possible, reply to [information], and then I can get the technical materials, electronic books, interview materials of first-line big factories and excellent resume templates carefully arranged by me.
The title
Given n non-negative integers to represent the height diagram of each column of width 1, calculate how much rain the columns in this order can catch after rain.
Example 1:
- Enter: height = [0,1,0,2,1,0,1,3,2,1,2,1,2,1]
- Output: 6
- Explanation: the height diagram above is represented by the array [0,1,0,2,1,0,1,3,2,1,2,1,1], in which case 6 units of rain can be caught (the blue parts are rain).
Example 2:
- Enter: height = [4,2,0,3,2,5]
- Output: 9
prompt
- n == height.length
- 0 <= n <= 3 * 104
- 0 <= height[i] <= 105
LeetCode
Method a
Violent method, we can treat each element of the array as a bucket, so that we can calculate the amount of water each bucket is connected to, all of them can be added up. How do you know how much water each bucket holds? So you just calculate the maximum column height on each side of the bucket, and then subtract the minimum of the two maximum heights from the height of the bucket which is the amount of water the bucket can hold.
The brute force method is simple, but the least efficient, because each element has to be traversed backwards and forwards, so the time is O(n^2). The space complexity is O(1).
package com.chenpi;
/ * * *@DescriptionAfter the rain *@Author Mr.nobody
* @Date 2021/6/14
* @Version1.0 * /
public class TrappingRainWater {
public static void main(String[] args) {
int[] height = {0.1.0.2.1.0.1.3.2.1.2.1};
TrappingRainWater tr = new TrappingRainWater();
System.out.println(tr.trap(height));
}
public int trap(int[] height) {
// Store the total amount of rainwater
int total = 0;
int size = height.length;
// Iterate over each element and calculate the amount of water in each bucket
for (int i = 1; i < size - 1; i++) {
// Scan left from the current bucket to find the highest column height, including its own height
int maxLeft = 0;
for (int j = i; j >= 0; j--) {
maxLeft = Math.max(maxLeft, height[j]);
}
// Scan from the current bucket to the right to find the highest column height, including its own height
int maxRight = 0;
for (int j = i; j < size; j++) {
maxRight = Math.max(maxRight, height[j]);
}
// The minimum of the two highest heights minus their own height is the current bucket of water
total += Math.min(maxLeft, maxRight) - height[i];
}
returntotal; }}Copy the code
Method 2
In terms of maximum value problems, the most important thing we should think about is whether we can use dynamic programming. In the brute force method, we need to calculate the maximum column height on each side of the bucket every time we calculate the amount of water in the bucket. Is it possible to calculate the maximum column height on both sides of the next bucket according to the calculated maximum column height? Dynamic programming algorithms can do that.
- The left maximum height of the first element must be equal to itself, so the left maximum height of each subsequent element is equal to the maximum height of the left maximum height of the previous element and the height of the current element.
- If you walk left from the right of the array, the maximum right height of the first element must be equal to itself, so the maximum right height of each successive element is equal to the maximum right height of the previous element and the height of the current element.
- Finally, according to the two maximum height arrays calculated in the previous two steps, the water connection of each element can be calculated.
We need to traverse the array twice to find the maximum left and right height, and traverse the maximum height array to find the total water connection, so the time complexity is O(n). Space complexity is O(n).
package com.chenpi;
/ * * *@DescriptionAfter the rain *@Author Mr.nobody
* @Date 2021/6/14
* @Version1.0 * /
public class TrappingRainWater {
public static void main(String[] args) {
int[] height = {0.1.0.2.1.0.1.3.2.1.2.1};
TrappingRainWater tr = new TrappingRainWater();
System.out.println(tr.trap(height));
}
public int trap(int[] height) {
if (null == height || height.length == 0) {
return 0;
}
// Store the total amount of rainwater
int total = 0;
int size = height.length;
// Store the maximum left height of each element
int[] leftMax = new int[size];
// The maximum left height of the first element on the left must be equal to its own height
leftMax[0] = height[0];
for (int i = 1; i < size; i++) {
// The maximum left height of each element is equal to the maximum left height of the previous element and the maximum height of the current element
leftMax[i] = Math.max(height[i], leftMax[i - 1]);
}
// Store the maximum right height of each element
int[] rightMax = new int[size];
// The maximum right height of the first element on the right must be equal to its own height
rightMax[size - 1] = height[size - 1];
for (int i = size - 2; i >= 0; i--) {
// The maximum right height of each element is equal to the maximum right height of the previous element and the maximum height of the current element
rightMax[i] = Math.max(height[i], rightMax[i + 1]);
}
for (int i = 1; i < size - 1; i++) {
// Calculate the water connection of each element
total += Math.min(leftMax[i], rightMax[i]) - height[i];
}
returntotal; }}Copy the code
Previous problem and next problem
LeetCode 1 of the Day “Determine whether to rearrange characters for each other”
Next question: LeetCode of the Day question: LeetCode of the Day question: “Roman numerals to integers”