Four solutions to AC this hard problem: from "naive solution" to "area difference" method | Java

4.solutions to AC this hard problem: from "naive solution" to "area difference" method | Java

This article is participating in the "Java Topics month - Java brush title punch" to view details about active links

Title description

This is the LeetCode 42. The rainwater , the difficulty is difficult .

Tag: "Monotone Stack", "Mathematics"

Given n non-negative integers representing the height map of each column with a width of 1, calculate how much rain can be received by the columns arranged in this way after it rains.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above is the height map represented by the array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain can be received ( The blue part represents rain). Copy code

Example 2:

Input: height = [4,2,0,3,2,5] Output: 9 Copy code

prompt:

  • n == height.length
  • 0 <= n <= 3 * 10410^4
  • 0 <= height[i] <= 10510^5

Naive solution

For each column, we only need to find the "highest column on the left" and "the highest column on the right".

Take a minimum value for the highest pillar on the left and right, and compare it with the height of the current pillar to get the rainwater that can be received at the current position.

At the same time, the pillars on the edge cannot receive rainwater (there is no pillar on one side).

Such an approach is a "violent approach", but the title does not give the data scope, and we cannot analyze whether it is AC.

It s over~ (Good question, I suggest joining the Blue Bridge Cup

Code:

class Solution { public int trap ( int [] height) { int n = height.length; int ans = 0 ; for ( int i = 1 ; i <n- 1 ; i++) { int cur = height[i]; //Get the maximum value of the left side of the current position int l = Integer.MIN_VALUE; for ( int j = i- 1 ; j >= 0 ; j--) l = Math.max(l, height[j]); if ( l <= cur) continue ; //Get the maximum value of the right side of the current position int r = Integer.MIN_VALUE; for ( int j = i + 1 ; j <n; j++) r = Math.max(r, height[j]); if (r < = cur) continue ; //Calculate the rainwater available at the current location ans += Math.min(l, r)-cur; } return ans; } } Copy code
  • Time complexity: all non-edge pillars need to be processed, and the complexity is O(n)O(n) ; For each column, you need to scan on both sides to find the maximum value, the complexity isO(n)O(n) . The overall complexity isO(n2)O(n^2)
  • Space complexity:O(1)O(1)

Preprocessing maximum value solution

The idea of naive solution is there, we think about how to optimize it.

In fact, any optimization is nothing more than "reducing duplication."

Think about which links in the simple thinking are more time-consuming, and where in the time-consuming links are repetitive and can be optimized.

1. traverse each pillar to find out how much rainwater each pillar can receive. This O(n)O(n) operation will definitely not be saved.

But when calculating how much rainwater can be received by a certain column, it is necessary to scan both sides to find the maximum value on both sides. Each column is scanned like this, resulting in every position being scannednn times. This process is obviously optimizable.

In other words: we hope to find the maximum value on both sides of any position by non-repetitive traversal.

The problem is transformed into: Given an array, how to find the maximum value of the left half and the maximum value of the right half at any position.

A very intuitive solution is to directly store the maximum value on both sides of a certain position.

We can start from the two ends separately and preprocess the "left and right best value" of each position, which can reduce the complexity of our "finding the left and right best value" to O(1)O(1) .

The complexity of the overall algorithm also changes from O(n2)O(n^2)drop toO(n)O(n) .

Code:

class Solution { public int trap ( int [] height) { int n = height.length; int ans = 0 ; //When preprocessing the most value, we will directly access height[0] or height[n-1 ], so we have to judge if (n == 0 ) return ans; //Preprocess the leftmost value of each position int [] lm = new int [n]; lm[ 0 ] = height[ 0 ]; for ( int i = 1 ; i <n; i++) lm[i] = Math.max(height[i], lm[i- 1 ]); //Preprocess the most value on the right of each position int [] rm = new int [n]; rm[n- 1 ] = height[n- 1 ]; for ( int i = n- 2 ; i >= 0 ; i--) rm[i] = Math.max(height[i], rm[i + 1 ]); for ( int i = 1 ; i <n- 1 ; i++) { int cur = height[i]; int l = lm[i]; if (l <= cur) continue ; int r = rm[i]; if (r <= cur) continue ; ans += Math.min(l, r)-cur; } return ans; } } Copy code
  • Time complexity: preprocess the two maximum value arrays, the complexity is O(n)O(n) ; Calculate the amount of rainwater that each pillar can receive, the complexity isO(n)O(n) . The overall complexity isO(n)O(n)
  • Space complexity: an array is used to store the maximum value on both sides. The complexity isO(n)O(n)

Monotonic stack solution

As we mentioned earlier, the optimization idea turns the problem into: Given an array, how to find the maximum value of the left half and the maximum value of the right half at any position.

But think about it carefully, in fact, we don't need to find the maximum value on both sides, we only need to find the closest pillar on both sides that is higher than the current position.

For this kind of problem of finding the nearest value, there is a general solution: monotonic stack .

A monotonic stack is actually to maintain a monotonic stack of elements on the basis of the stack.

In this question, because we need to find a certain position on both sides of the pillars higher than the current position (only on both sides of the pillars higher than the current position, the current position can receive rain), we can maintain the monotonic decrease of the elements in the stack.

PS. Find the most recent value larger than it on a certain side, and use the monotonic stack to keep the elements in the stack decreasing; find the nearest value on a certain side that is smaller than it, and use the monotonic stack to keep the elements in the stack increasing...

When an element at a certain position pops out of the stack, such as position

a
, We can naturally get
a
Position side ratio
a
High pillar:

  • One is leading to
    a
    The column where the position element pops up (
    a
    Right side ratio
    a
    High pillar)
  • one is
    a
    The top element of the stack after popping the stack (
    a
    Left side ratio
    a
    High pillar)

When there is

a
Ratio of left and right sides
a
After the high column, you can calculate
a
The amount of rainwater that the location can receive.

Code:

class Solution { public int trap ( int [] height) { int n = height.length; int ans = 0 ; Deque<Integer> d = new ArrayDeque<>(); for ( int i = 0 ; i <n; i++) { while (!d.isEmpty() && height[i]> height[d.peekLast()]) { int cur = d.pollLast(); //If there is no element in the stack, it means that there is no higher column to the left of the current position, skip if (d.isEmpty()) continue ; //left position, and the left and right position of stars "width" and "height" int L = d.peekLast (), I = R & lt; int W = R & lt - L + . 1 - 2 ; int H = Math.min (height [l], height[r])-height[cur]; ans += w * h; } d.addLast(i); } return ans; } } Copy code
  • Time complexity: Each element is pushed and popped on the stack at most once. The complexity isO(n)O(n)
  • Space complexity: the stack has the most storage nn elements. The complexity isO(n)O(n)

Area difference solution

In fact, we can also use the "area difference" to solve.

Let s first calculate the "pillar area"sumsum and "the area of a rectangle with the number of columns as the width and the highest column height as the height"fullfull .

Then calculate the maximum height coverage area once "from left to right" and "from right to left" respectively lSumlSum andrSumrSum .

Obviously there will be repeated areas, and the repeated areas will only appear on the left and right of the "mountain" independently.

Using this feature, we can solve the "rainwater area" through a simple equation relationship:

Code:

class Solution { public int trap ( int [] height) { int n = height.length; int sum = 0 , max = 0 ; for ( int i = 0 ; i <n; i++) { int cur = height[i]; sum += cur; max = Math.max(max, cur); } int full = max * n; int lSum = 0 , lMax = 0 ; for ( int i = 0 ; i <n; i++) { lMax = Math.max(lMax, height[i]); lSum += lMax; } int rSum = 0 , rMax = 0 ; for ( int i = n- 1 ; i >= 0 ; i--) { rMax = Math.max(rMax, height[i]); rSum += rMax; } return lSum + rSum-full-sum; } } Copy code
  • time complexity:O(n)O(n)
  • Space complexity:O(1)O(1)

summary

From "naive solution" to "pre-processing maximum value" to "monotonic stack" and finally to "area difference solution", have you learned it?

Among them, "monotonous stack" is the most conventional, and it is also the interviewer's favorite to consider what to eat. It is recommended to focus on it~