当前位置：网站首页>[array]bm94 rainwater connection problem - difficult

[array]bm94 rainwater connection problem - difficult

2022-06-27 03:49:00 【51CTO】

Knowledge point Double pointer Monotonic stack Dynamic programming

describe

Given an array of integers arr, It is known that all values are nonnegative , Think of this array as a column height map , Calculate columns arranged in this way , How much rain can be received after rain .( The height of the area outside the array is treated as 0) [ Array ]BM94 The rain problem - More difficult _ Double pointer

Data range ： The length of the array [ Array ]BM94 The rain problem - More difficult _ Array _02 , Each value in the array satisfies , Ensure that the returned results meet requirement ： Time complexity

Example 1

Input ：

      
      
       
       [3,1,2,5,2,4]
      
      
      
      
       
       1.

Copy the return value ：

Copy instructions ：

      
      
       
        Array  [3,1,2,5,2,4]  A diagram showing the height of the column , under these circumstances , Can connect  5 Units of rain , Blue is rain  , As shown in the figure .
      
      
      
      
       
       1.

Example 2

Input ：

      
      
       
       [4,5,1,3,2]
      
      
      
      
       
       1.

Copy the return value ：

Answer key

Auxiliary array solution

Ideas ：

Let's say the array is a, For any subscript i, Its capacity to hold water depends on the highest water on its left and right sides 2 The one with the lowest root , Suppose the height is h, The capacity for holding water is h - a[i]. We just find out for any of the following tables i, It is the highest around

Steps are as follows ：

The trial 2 An array max_left[i] and max_right[i] Represent the subscript respectively i When , On the left [0,i-1] The highest pillar , And from right to left [n-1,i+1] The highest pillar , Traversal array , First solve these two arrays
Traversal array again , When the subscript is reached i When , The capacity of this column to hold water is v = min(max_left[i],max_right[i]) - arr[i]
Accumulate the second step to get the answer

The code is as follows ：

       
       // https://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D295
       
       #include <bits/stdc++.h>
       
       using 
       
       namespace 
       
       std;
       
       long 
       
       long 
       
       maxWater(
       
       vector
       
       <
       
       int
       
       > 
       
       &
       
       arr)
       
{
       
       if (
       
       arr.
       
       size() 
       
       <= 
       
       2)
       
  {
       
       return 
       
       0;
       
  }
       
       std::vector
       
       <
       
       int
       
       > 
       
       max_left(
       
       arr.
       
       size(), 
       
       0);
       
       std::vector
       
       <
       
       int
       
       > 
       
       max_right(
       
       arr.
       
       size(), 
       
       0);
       
       for (
       
       int 
       
       i 
       
       = 
       
       1; 
       
       i 
       
       < 
       
       arr.
       
       size(); 
       
       ++
       
       i)
       
  {
       
       max_left[
       
       i] 
       
       = 
       
       std::max(
       
       max_left[
       
       i 
       
       - 
       
       1], 
       
       arr[
       
       i 
       
       - 
       
       1]);
       
  }
       
       for (
       
       int 
       
       i 
       
       = 
       
       arr.
       
       size() 
       
       - 
       
       2; 
       
       i 
       
       >= 
       
       0; 
       
       --
       
       i)
       
  {
       
       max_right[
       
       i] 
       
       = 
       
       std::max(
       
       max_right[
       
       i 
       
       + 
       
       1], 
       
       arr[
       
       i 
       
       + 
       
       1]);
       
  }
       
       int 
       
       res 
       
       = 
       
       0;
       
       for (
       
       int 
       
       i 
       
       = 
       
       0; 
       
       i 
       
       < 
       
       arr.
       
       size(); 
       
       ++
       
       i)
       
  {
       
       int 
       
       h 
       
       = 
       
       std::min(
       
       max_left[
       
       i], 
       
       max_right[
       
       i]);
       
       if (
       
       h 
       
       > 
       
       arr[
       
       i])
       
    {
       
       res 
       
       += (
       
       h 
       
       - 
       
       arr[
       
       i]);
       
    }
       
  }
       
       return 
       
       res;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.

Double pointer solution

In the above solution, we use 2 An auxiliary array to hold a subscript i Maximum left and right height of . So can we know the subscript without using the auxiliary array i The maximum left and right height of ？ In fact, it's easy to know when you think about it , It's easy to write an answer with two pointers .

step ：

Use 2 A variable left_hight and right_hight The maximum height of the leftmost and rightmost code respectively
Use 2 A pointer to the i and k Respectively from the 0 and n-1 Start traversing at the location of

If a[i] < left_hgith && a[i] < right_hight, Then the index is i The location of the can accommodate min(left_hight,right_hight)-a[i] Of water
If a[i] >= left_hight && a[i] <= right_hight, take i Move right
If a[i] >= left_hight && a[i] >= right_hight, take k Move left

       
       long 
       
       long 
       
       maxWater(
       
       const 
       
       vector
       
       <
       
       int
       
       > 
       
       &
       
       arr)
       
{
       
       if (
       
       arr.
       
       size() 
       
       <= 
       
       2)
       
  {
       
       return 
       
       0;
       
  }
       
       //  Left and right hands 
       
       int 
       
       left 
       
       = 
       
       0;
       
       int 
       
       right 
       
       = 
       
       arr.
       
       size() 
       
       - 
       
       1;
       
       //  stay [left,right] It is the highest on the left outside the section 、 The highest on the right 
       
       int 
       
       left_max 
       
       = 
       
       0;
       
       int 
       
       right_max 
       
       = 
       
       0;
       
       int 
       
       res 
       
       = 
       
       0;
       
       while (
       
       left 
       
       <= 
       
       right)
       
       //  Traverse the entire array 
       
  {
       
       //  Get the height of the short side 
       
       int 
       
       min_hight 
       
       = 
       
       std::min(
       
       left_max, 
       
       right_max);
       
       res 
       
       += 
       
       std::max(
       
       0, 
       
       min_hight 
       
       - 
       
       std::min(
       
       arr[
       
       left], 
       
       arr[
       
       right]));
       
       //  Accumulate the capacity that the current index can hold 
       
       left_max 
       
       = 
       
       std::max(
       
       left_max, 
       
       arr[
       
       left]);
       
       //  Update left height 
       
       right_max 
       
       = 
       
       std::max(
       
       right_max, 
       
       arr[
       
       right]);
       
       //  Update right height 
       
       if (
       
       arr[
       
       left] 
       
       < 
       
       arr[
       
       right])
       
       //  Update index , Move the shorter side towards the middle 
       
    {
       
       left
       
       ++;
       
    }
       
       else
       
    {
       
       right
       
       --;
       
    }
       
  }
       
       return 
       
       res;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.