Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Spring Recruit punch card day 11 chapter 14.

Study like the seedlings of spring, see its increase, day has a director; Drop out of school such as a whetstone, see its loss, loss.

There are so many activities in digging gold. This month, I decided to use GO to brush the questions every day, on the one hand, to improve the algorithm level, on the other hand, to settle the learning of GO language.

Let’s GO!

Topic describes

Given an integer array height of length n. There are n perpendicular lines, and the two ends of the i-th line are (I, 0) and (I, height[I]).

Find the two lines that together with the X-axis will hold the most water.

Returns the maximum amount of water a container can hold.

Note: You cannot tilt the container.

The sample

Example 1:

Input:,8,6,2,5,4,8,3,7 [1]

Output: 49

Explanation: the vertical lines represent the input array [1,8,6,2,5,4,8,3,7]. In this case, the maximum amount of water the container can hold (shown in blue) is 49.

Example 2:

Enter: height = [1,1]

Output: 1.

Tip:

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

Their thinking

  1. The first thing that comes to mind when you look at this is, if you have the highest left and right sides, then you have the most water. Take a step back and think about it. The higher the line near the two ends, the more water it holds.
  2. We can follow this idea to achieve, that is, assuming that the two sides can hold the most water at the highest, and then like the inside, if the inside line is higher, it means that the outside line is not the highest.
  3. But during the period, I encountered the problem of pass rate, so I brushed the problem of force buckle and foundDouble pointerThat’s a good idea. The reason WHY I have the pass rate problem is that I didn’t take into account:The distance between the two sides of the same height is the best
  4. There are also performance optimizations: the area calculation is constrained by the shorter edge, so we can reduce unnecessary operations when we use the dual pointer to calculate the interview, i.e., move the shorter edge inward.

AC code

func maxArea(height []int) int {
	i := 0
	j := len(height) - 1
	var ret int
	for i < j {
        var area int
		if height[i] > height[j]{
			area = (j-i)* height[j]
		}else {
			area = (j-i)* height[i]
		}
		if area > ret {
			ret = area
		}
		if height[i] < height[j] {
			i++
		}else {
			j--
		}
	}
	return ret
}
Copy the code

The results

conclusion

Today I learned the idea of double pointer. I have brushed so many questions this month. Today I feel the happiness of brushing questions for the first time.

The time complexity is O(n) and the space complexity is O(1).

sources

Source: LeetCode

Link: leetcode-cn.com/problems/co…

Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

The last

Thanks for reading and welcome to like, favorites,coin(attention)!!