题目链接

11. 盛最多水的容器 - 力扣（LeetCode）

题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

题目示例

示例 1 :

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2 :

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

解题思路

1. left 指向最左边的数组, right 指向最右边的数组
2. 怎么去利用双指针找最大盛水量呢, 宽度为 right - left, 高度为 min(height[right], height[left])
3. 如果移动的话, 哪一个边比较小, 就去移动那个边

题解代码

Java 代码 :

class Solution {
    public int maxArea(int[] height) {
        int res = 0, left = 0, right = height.length - 1;
        while(left < right){
            // 面积 = 高 × 宽 (高要取最短的那条, 短板效应)
            int area = Math.min(height[left], height[right]) * (right - left);
            res = Math.max(area, res);

            // 收缩两边界
            if(height[left] < height[right]){
                left++;
            } else {
                right--;
            }
        }

        return res; 
    }
}

复杂度分析

• 时间复杂度: 只需要一次遍历数组，left 和 right 指针各自向中间靠拢，因此时间复杂度为 O(n)，其中 n 是数组的长度。
• 空间复杂度: 只使用了常数级别的额外空间，主要是用来存储 res、left 和 right，因此空间复杂度为 O(1)。