Leetcode 11. 盛最多水的容器 (详细解析加JAVA代码)

题目描述

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

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

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

说明：你不能倾斜容器。

解题思路

指针法：

复杂度分析

时间复杂度 O(N)： 双指针遍历一次底边宽度 NN​ 。

空间复杂度 O(1) ： 变量 i , j , res使用常数额外空间。

思路和算法一

首先明确一下容器容量的计算公式，这里简化为计算两条垂线和x轴围成的长方形面积。

根据短板效应：面积等于两条垂线中短的那一条 乘以 两条垂线的x轴距离。

即：S(i,j) = min(h[i],h[j]) × (j−i) （i,j分别为两条垂线的x轴坐标）

其次，我们要考虑怎么找到最大的面积？

肯定是通过移动指针选择不同的柱子来完成：

我们定义左右指针，初始分别指向最左边的柱子和最右边的柱子。

每次移动的时候：都将高度低的柱子指针向内移动一格。直至两者相遇，比较所有面积，找到最大值。

你们可以先看完下面的图理解一下。

注意：聪明的你有没有发现Bug?如图这样双指针往中间移动时，是不是没有计算所有矩形面积？会不会漏掉某些情况呢？

解释如下：第一次我们看到的矩形为1*8=8，

• 如果将高的柱子向内移动，限制于短边，水槽的高度不会变，但是底会越来越小。因此下个水槽的面积 一定变小。

• 如果将低的柱子向内移动，我们无法判断水槽高度怎么变化，但是底会越来越小。因此下个水槽的面积 可能会增大。

• 所以，从感官上讲，我们应该要将低的柱子向内移动。

到这，可能还会有些小伙伴不认可，觉得可能会有个别特殊情况没有被考虑，结果不一定是最大值。我们接着分析：

• 因为这样移动，我们可以保证每次取到的水槽面积一定是该高度下最大的。

• 例如图一，当H=1，底最长时，面积最大。

• 图二，当H=7（最右边的柱子的高），底最大=8-1，因为如果左柱再向左边移动就会比右柱矮，H就不等于7了。

• 图三及后面的都一样。

综上所述，我们找到了所有高度下的最大面积，再从中选取最大值，就一定能够找到水槽的最大面积。

如图：

代码

class Solution {
    public int maxArea(int[] height) {
        int res = 0; 
        int i = 0; //左柱指针
        int j = height.length - 1; 右柱指针
        while (i < j) {
            int area = (j - i) * Math.min(height[i], height[j]); //面积公式
            res = Math.max(res, area); //记录所有更新的最大面积
            if (height[i] < height[j]) {
                i++; //height[i] < height[j]，左柱指针右移
            } else {
                j--; //height[i] > height[j]，右柱指针左移
            }
        }
        return res;
    }
}