【力扣 - 盛最多水的容器】

题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例1

示例2

输入：height = [1,1]
输出：1

提示：

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

题解

双指针

1：使用两个指针，indexLeft和indexRight
2：面积的计算公式Area = high * wide，面积等于高 * 宽
3：计算high = fmin(height[indexRight] , height[indexLeft])
4: 计算wide = indexRight - indexLeft
5：计算出对应的Area与maxArea进行比较并更新maxArea
6: 移动indexRight 与 indexLeft中小的指针
时间复杂度：O(n)
空间复杂度：O(1)

代码

int maxArea(int* height, int heightSize)
{
    // Initialize two pointers, one at the start and one at the end of the array
    int indexLeft = 0;
    int indexRight = heightSize - 1;
    
    // Initialize the variable to store the maximum area
    int maxArea = 0;
    
    // Loop until the two pointers meet
    while (indexLeft < indexRight)
    {
        // Calculate the height of the container at the current positions
        int minHeight = fmin(height[indexLeft], height[indexRight]);
        
        // Calculate the width of the container
        int width = indexRight - indexLeft;
        
        // Calculate the area of the container
        int area = width * minHeight;
        
        // Update the maximum area if the current area is greater
        if (maxArea < area)
        {
            maxArea = area;
        }
        
        // Move the pointer with the smaller height towards the center
        if (height[indexLeft] < height[indexRight])
        {
            indexLeft++;
        }
        else
        {
            indexRight--;
        }
    }
    
    // Return the maximum area found
    return maxArea;
}
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
37
38
39
40
41