盛最多水的容器

发表于 分类于 阅读次数：

盛最多水的容器（难度：中等）

1

方法：双指针

思路

两线段之间形成的区域总是会受到其中较短那条长度的限制。此外，两线段距离越远，得到的面积就越大。

算法
  • 在由线段长度构成的数组中使用两个指针，一个放在开始，一个置于末尾。
  • 使用变量 max_area来持续存储到目前为止所获得的最大面积。
  • 在每一步中，我们会找出指针所指向的两条线段形成的区域，更新 max_area，并将指向较短线段的指针向较长线段那端移动一步。
复杂度

时间复杂度：O(n)，一次扫描。

空间复杂度：O(1)，使用恒定的空间。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int max_area = 0;

        while(left < right){
            max_area = Math.max(max_area, Math.min(height[left],height[right]) * (right-left));
            if(height[left] < height[right])
                left++;
            else
                right--;
        }

        return max_area;
        
    }
}
2