“This is my 7 days to participate in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.

preface

I have been planning to learn data structures and basic algorithms, but I have seen them in fits and starts. Now I’m determined to stick to it. I’m going to start with LeetCode’s HOT100 and finish 1~2 exercises every day, hoping to develop the habit of continuous learning in this way. Because I am doing iOS development, mainly using Objective-C language, and I am also learning Swift recently, all the questions in this series will be solved by Swift language. What is updated in this paper is 011, the seventh question of HOT100 in LeetCode that holds the most water.

The title

Give you n non-negative integers A1, A2… , an a1, a2… , ana1, A2… , an, each number represents a point in the coordinates (I, AI)(I, ai)(I, ai). Draw n vertical lines in coordinates, and the two endpoints of vertical line I are (I, AI)(I, ai)(I, ai)(I, ai) and (I,0)(I,0)(I,0). Find the two lines that together with the X-axis will hold the most water. Note: You cannot tilt the container. Example 1:

,8,6,2,5,4,8,3,7 input: [1] output: 49 explanation: the figure in the vertical line represents the input array,8,6,2,5,4,8,3,7 [1]. In this case, the maximum amount of water the container can hold (shown in blue) is 49.Copy the code

Example 2:

Input: height = [1,1Copy the code

Example 3:

Input: height = [4,3,2,1,4Copy the code

Example 4:

Input: height = [1,2,1Copy the code

Tip:

n == height.length
2 <= n <= 105
0 <= height[i] <= 104
Copy the code

Analysis of the

The amount of water a barrel can hold depends on the shortest piece of wood. Sij=(j− I)∗min(ai, aj), assuming I

In each state, regardless of whether the long plate or the short plate is narrowed by one slot to the middle, the bottom edge of the tank will be shortened by −1:

  • If the short plate is moved inward, the short plate min(H [I], H [j])min(H [I], H [j])min(H [I], H [j]) of the flume may become larger, so the area of the next flume may increase.
  • If the long plate is moved inward, the short plate min(H [I], H [j])min(H [I], H [j])min(H [I], H [j]) of the flume remains unchanged or becomes smaller, so the area of the next flume must become smaller.

Therefore, initialize the two Pointers to separate the left and right ends of the sink, move the short board inward one space in each cycle, and update the maximum area until the two Pointers jump out when they meet. Can obtain the maximum area.

The basic flow of the two-pointer method is as follows:

1. Initialization: set the double pointer left and the initial value of right respectively points to the left and right subscripts of the sink; Set the initial value of maxArea to 0, indicating the current maximum capacity. MaxArea = min(h[left],h[right]) × (right − left); maxArea = maxArea = maxArea If h[left] <= h[right], move left to the right until the new left value is greater than the original left value. If h[left] < h[right], move left to the right. Move right to the left until the value of the new right is greater than the value of the original rightCopy the code

The complexity of this method is O(n), which is simpler than the violent solution.

Answer key

class KLLC011 { 
    
    func maxArea(_ height: [Int]) -> Int { 
        / / initialization
        var left = 0, right = height.count - 1 
        var maxArea = 0 
        // If the loop ends with left >= right, the loop continues with left < right
        while left < right { 
            // Calculate the volume of the current left right
            let curH = min(height[left], height[right]) 
            let curArea = curH * (right - left) 
            / / update the maxArea
            if maxArea < curArea { 
                maxArea = curArea 
            } 
            // Move inward according to the size of the left right value
            if height[left] < = height[right] { 
                //h[left] <= h[right], then move left to right until the new left value is greater than the original left value
                repeat { 
                    left + = 1 
                } while left < right && curH > = height[left] 
            } else { 
                //h[left] < h[right], then move right to the left until the value of the new right is greater than the value of the original right
                repeat { 
                    right - = 1 
                } while left < right && curH > = height[right] 
            } 
        }
        // Return the maximum volume
        return maxArea 
    } 
}
Copy the code