Leecode11. The container with the most water -- leecode100 questions series

I'm Xiao Zhang , Determined to use the most concise code to do the most efficient expression


The following is my personal solution , Each problem includes all solutions as much as possible , And achieve the optimal solution , Welcome to collect ! Leaving a message. !

Portal ——>Leecode Big factory hot topic 100 Tao series problem solution


Problem description

Here you are. n Nonnegative integers a1,a2,…,an, Each number represents a point in the coordinate (i, ai) . Draw in coordinates n Bar vertical line , Vertical line i The two endpoints of are (i, ai) and (i, 0) . Find two of them , Make them x A container of shafts can hold the most water .

explain : You can't tilt the container .

Example 1:
Input :[1,8,6,2,5,4,8,3,7]
Output :49
explain : The vertical line in the figure represents the input array [1,8,6,2,5,4,8,3,7]. In this case , The container can hold water ( In blue ) The maximum value of is 49.

Example 2:
Input :height = [1,1]
Output :1

Example 3:
Input :height = [4,3,2,1,4]
Output :16

Example 4:
Input :height = [1,2,1]
Output :2

Tips :
n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4


Ideas : Double finger needling

The area depends on the short board .

① Therefore, even if a longer plate is encountered when the long plate moves inward , The area of the rectangle will not change ; When you encounter a shorter board , The area will become smaller .
② So you want the area to get bigger , Only the short board can move inward ( Because the moving direction is fixed ), Of course, it is also possible to make the area smaller , But only in this way can there be the possibility of making the area larger


class Solution {

public:
int maxArea(vector<int>& height) {

int maxArea = 0, i = 0, j = height.size();
while(i < j) {

maxArea = max(maxArea, (j-i) * min(height[i], height[j]));
height[i] < height[j] ? i++ : j--;
}
return maxArea;
}
};
Please bring the original link to reprint ,thank
Similar articles

2021-10-14