【LC100】No11. 盛最多水的容器

题目描述

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

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

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

说明：你不能倾斜容器。

提示：

• n == height.length

• 2 <= n <= 105

• 0 <= height[i] <= 104

示例

示例 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

链接

思路

相当于计算最大乘积，首先我们很好想到使用双指针，分别从左右两边开始移动。

横边为左右两指针之间的差值，而由于是用来盛水，所有竖边取左右两边中的短边。

我们利用贪心的思想——

左右指针初始指向下标 0 和下标 length - 1。

乘积由短边决定，所以为了使得能获得最大乘积，我们放弃左右两条竖边种较短的那条，将指针向中间移动，以寻求找到比被放弃的短边更长的边。

简而言之，每一步都是在“抛弃最短，找更长”。

解法一：双指针

代码

class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length == 1) {
            return 0;
        }
        int left = 0, right = height.length - 1;
        int max = 0;
        while (left < right) {
            int currentMax = (right - left) * Math.min(height[left], height[right]);
            max = Math.max(max, currentMax);
            if (height[right] < height[left]) {
                right--;
            } else {
                left++;
            }
        }
        return max;
    }
}

• 时间复杂度：O(n)

• 空间复杂度：O(1)