LeetCode【11】-- 盛水最多的容器

秦怀杂货店

发布于 2022-02-15 14:50:38

4290

💻 剑指Offer & LeetCode刷题仓库：https://github.com/Damaer/CodeSolution
- 文档地址：https://damaer.github.io/CodeSolution/
- 仓库介绍：刷题仓库：CodeSolution
📒 编程知识库：https://github.com/Damaer/Coding
- 文档地址：https://damaer.github.io/Coding/#/

题目

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。来源：力扣（LeetCode）

示例：

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

思路与解答

这道题的是要找出最大的容器，最大的容器是怎么算的呢？

容器大小 = 长 * 宽

长其实就是我们两个索引之间的距离，宽就是该索引位置的数值（两个索引取最短）。

要想容器大小最大，无非两个索引距离很大，或者索引位置的数组很大，或者两者兼有。那我们先用两个索引，也就是双指针，分别从左右两边开始往中间遍历。这个时候，我们保证了一开始的长度就是最长的，只要找到更高的，就一定是容器体积较大的。

具体的步骤如下：

1.初始化最大容器，两个指针分别在两端的时候的容器大小
2.左边指针往中间走，右边指针也往中间走，直到两个指针相遇。
- 如果左边指针所指的数值比较小，那么左边指针向右边移动，否则右边的指针向左边移动。

之所以是数值较小的指针移动，是因为要想容器变大，那么需要将较矮的数值拉高，就像是木桶原理，木桶能装的水，是由最短的“板”决定的，因此需要寻找更高的”板“。

Java 代码如下：

class Solution {
 public static int maxArea(int[] height) {
        if (height == null || height.length == 0 || height.length == 1) {
            return 0;
        }
        int i = 0;
        int j = height.length-1 ;
        int sum = (j - i ) * Math.min(height[i], height[j]);
        while (i != j) {
            int num = (j - i ) * Math.min(height[i], height[j]);
            if (num > sum) {
                sum = num;
            }
            if (height[i] >= height[j]) {
                j--;
            } else {
                i++;
            }
        }
        return sum;
    }
}

C++ 代码实现：

class Solution {
public:
    int maxArea(vector<int>& height) {
        if (height.size()== 0 ||height.size()== 1) {
            return 0;
        }
        int i = 0;
        int j = height.size()-1 ;
        int sum = (j - i ) * min(height[i], height[j]);
        while (i != j) {
            int num = (j - i ) * min(height[i], height[j]);
            if (num > sum) {
                sum = num;
            }
            if (height[i] >= height[j]) {
                j--;
            } else {
                i++;
            }
        }
        return sum;
    }
};

【作者简介】

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，Redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

平日时间宝贵，只能使用晚上以及周末时间学习写作 - END -

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-11-17，如有侵权请联系 cloudcommunity@tencent.com 删除

容器