Leetcode 011. 盛最多水的容器

[meibin08]

题目描述

给你 n 个非负整数 a1，a2，...，a``n，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 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

示例 3：

输入：height = \[4,3,2,1,4\]
输出：16

示例 4：

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

提示：

• n = height.length
• 2 <= n <= 3 * 104
• 0 <= height[i] <= 3 * 104

难度：

• 难度：中等
• 支持语言：JavaScript、Python、C++

相关标签

• 双指针

相关企业

• 字节
• 腾讯
• 百度
• 阿里

复杂度分析

• 时间复杂度：由于左右指针移动的次数加起来正好是 n， 因此时间复杂度为 $O(N)$。
• 空间复杂度：$O(1)$。

思路 1（javascript）:

题目中说找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。 ，因此符合直觉的解法就是固定两个端点，计算可以承载的水量， 然后不断更新最大值，最后返回最大值即可。这种算法，需要两层循环，时间复杂度是 $O(n^2)$。

代码（JS）:

let max = 0;
for (let i = 0; i < height.length; i++) {
  for (let j = i + 1; j < height.length; j++) {
    const currentArea = Math.abs(i - j) * Math.min(height[i], height[j]);
    if (currentArea > max) {
      max = currentArea;
    }
  }
}
return max;

虽然解法效率不高，但是可以通过（JS 可以通过，Python 不可以，其他语言没有尝试）。那么有没有更优的解法呢？

我们来换个角度来思考这个问题，上述的解法是通过两两组合，这无疑是完备的。我们换个角度思考，是否可以:

• 先计算长度为 n 的面积
• 然后计算长度为 n-1 的面积
• ...
• 计算长度为 1 的面积。

很显然这种解法也是完备的，但是似乎时间复杂度还是 $O(n ^ 2)$, 不要着急，我们继续优化。

考虑一下，如果我们计算 n-1 长度的面积的时候，是可以直接排除一半的结果的。

如图：

比如我们计算 n 面积的时候，假如左侧的线段高度比右侧的高度低，那么我们通过左移右指针来将长度缩短为 n - 1 的做法是没有意义的，因为新形成的面积变成了(n-1) * heightOfLeft， 这个面积一定比刚才的长度为 n 的面积 （n * heightOfLeft） 小。

也就是说最大面积一定是当前的面积或者通过移动短的端点得到。

关键点解析

• 双指针优化时间复杂度

Js中文网 - 前端进阶资源教程 www.javascriptC.com,typescript 中文文档
Javascript中文网是以前端进阶资源教程分享为主的专业网站，包括：前端、大厂面试题、typescript教程、程序人生、React.js……等，以帮助开发者成长为愿景的社区

思路 2

• 这道题目看似简单，做起来才发现不容易。分治法、动态规划都用不上，要想得到 O(n)O(n) 的解法只有使用双指针一条路。即使看了答案知道了双指针解法，你也可能并不清楚这个解法为什么正确。为什么双指针往中间移动时，不会漏掉某些情况呢？

• 如果没有真正理解题目，即使一次对着答案做出来了，再次遇到这个题目，还是可能做不出来。要理解这道题的正确性和原理，需要从背后的缩减搜索空间的思想去考虑题解。下面我将用图片解释这道题的正确性和原理。

• 双指针解法的正确性

思路 3

• 算法流程： 设置双指针 iii,jjj 分别位于容器壁两端，根据规则移动指针（后续说明），并且更新面积最大值 res，直到 i == j 时返回 res。

• 指针移动规则与证明： 每次选定围成水槽两板高度 h[i]h[i]h[i],h[j]h[j]h[j] 中的短板，向中间收窄 111 格。以下证明：

• 设每一状态下水槽面积为 S(i,j)S(i, j)S(i,j),(0<=i<j<n)(0 <= i < j < n)(0<=i<j<n)，由于水槽的实际高度由两板中的短板决定，则可得面积公式 S(i,j)=min(h[i],h[j])×(j−i)S(i, j) = min(h[i], h[j]) × (j - i)S(i,j)=min(h[i],h[j])×(j−i)。

• 在每一个状态下，无论长板或短板收窄 111 格，都会导致水槽 底边宽度 −1-1−1：
  + 若向内移动短板，水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j]) 可能变大，因此水槽面积 S(i,j)S(i, j)S(i,j) 可能增大。
  + 若向内移动长板，水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j]) 不变或变小，下个水槽的面积一定小于当前水槽面积。

• 因此，向内收窄短板可以获取面积最大值。换个角度理解：
  + 若不指定移动规则，所有移动出现的 S(i,j)S(i, j)S(i,j) 的状态数为 C(n,2)C(n, 2)C(n,2)，即暴力枚举出所有状态。
  + 在状态 S(i,j)S(i, j)S(i,j) 下向内移动短板至 S(i+1,j)S(i + 1, j)S(i+1,j)（假设 h[i]<h[j]h[i] < h[j]h[i]<h[j] ），则相当于消去了 S(i,j−1),S(i,j−2),...,S(i,i+1){S(i, j - 1), S(i, j - 2), ... , S(i, i + 1)}S(i,j−1),S(i,j−2),...,S(i,i+1) 状态集合。而所有消去状态的面积一定 <=S(i,j)<= S(i, j)<=S(i,j)：

  • 短板高度：相比 S(i,j)S(i, j)S(i,j) 相同或更短（<=h[i]<= h[i]<=h[i]）；
  • 底边宽度：相比 S(i,j)S(i, j)S(i,j) 更短。
    + 因此所有消去的状态的面积都 <S(i,j)< S(i, j)<S(i,j)。通俗的讲，我们每次向内移动短板，所有的消去状态都不会导致丢失面积最大值 。

代码

JavaScript 实现

/**
 * @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍：前端中文网是以前端进阶资源教程分享为主的专业网站，包括：前端、大厂面试题、typescript教程、程序人生、React.js
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  if (!height || height.length <= 1) return 0;

  let leftPos = 0;
  let rightPos = height.length - 1;
  let max = 0;
  while (leftPos < rightPos) {
    const currentArea =
      Math.abs(leftPos - rightPos) *
      Math.min(height[leftPos], height[rightPos]);
    if (currentArea > max) {
      max = currentArea;
    }
    // 更新小的
    if (height[leftPos] < height[rightPos]) {
      leftPos++;
    } else {
      // 如果相等就随便了
      rightPos--;
    }
  }

  return max;
};

/**
  作者：li-zhui-zhui
  链接：https://leetcode-cn.com/problems/container-with-most-water/solution/11-sheng-zui-duo-shui-de-rong-qi-by-li-zhui-zhui/
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
    let res = 0, i = 0, j = height.length - 1, cur = 0;
    while (i < j) {
        let h = height[i] < height[j] ? height[i] : height[j];
        cur = h * (j - i);
        res = cur > res ? cur : res;
        if (height[i] < height[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
};

C++ 实现

class Solution {
public:
    int maxArea(vector<int>& height) {
        auto ret = 0ul, leftPos = 0ul, rightPos = height.size() - 1;
        while( leftPos < rightPos)
        {
            ret = std::max(ret, std::min(height[leftPos], height[rightPos]) * (rightPos - leftPos));
            if (height[leftPos] < height[rightPos]) ++leftPos;
            else --rightPos;
        }
        return ret;
    }
};

/*
作者：nettee
链接：https://leetcode-cn.com/problems/container-with-most-water/solution/on-shuang-zhi-zhen-jie-fa-li-jie-zheng-que-xing-tu/
*/
int maxArea(vector<int>& height) {
    int res = 0;
    int i = 0;
    int j = height.size() - 1;
    while (i < j) {
        int area = (j - i) * min(height[i], height[j]);
        res = max(res, area);
        if (height[i] < height[j]) {
            i++;
        } else {
            j--;
        }
    }
    return res;
}

Python 实现

class Solution:
    def maxArea(self, heights):
        l, r =  0, len(heights) - 1
        ans = 0
        while l < r:
            ans = max(ans, (r - l) * min(heights[l], heights[r]))
            if heights[r] > heights[l]:
                l += 1
            else:
                r -= 1
        return ans

# 作者：jyd
# 链接：https://leetcode-cn.com/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/
class Solution:
    def maxArea(self, height: List[int]) -> int:
        i, j, res = 0, len(height) - 1, 0
        while i < j:
            if height[i] < height[j]:
                res = max(res, height[i] * (j - i))
                i += 1
            else:
                res = max(res, height[j] * (j - i))
                j -= 1
        return res

# 作者：lxj618
# 链接：https://leetcode-cn.com/problems/container-with-most-water/solution/shuang-zhi-zhen-bian-li-by-lxj618/
class Solution:
    def maxArea(self, height: List[int]) -> int:

        # 长度不断缩短，缩短的过程中只缩短值小的一边
        ans = 0
        idx_1, idx_2 = 0, len(height)-1

        while idx_1 < idx_2:
            ans = max(ans, (idx_2-idx_1)*min(height[idx_1],height[idx_2]))

            if height[idx_1] < height[idx_2]:
                idx_1 += 1
            else:
                idx_2 -= 1

        return ans

其他

• 原题leetcode链接：11.container-with-most-water - https://leetcode-cn.com/problems/container-with-most-water/description/
• 合作方：JavaScript中文网 – 全球极客挚爱的技术成长平台
• 说明：leetcode 题解 | 每日一题🔥 所有题目并非全部为本人解答，部分为在复习学习中整理提取其他解题作者的优秀笔记，便于大家学习共同进步，如有侵权，请联系删除。