盛水最多的容器

 关注

“脚本之家

”，与百万开发者在一起

来源丨牛牛码特（ID：niuniu_mart）

作者丨牛牛码特

已获得原公众号授权转载

算法是面试中的核心要素，如果在面试中算法没做出来，就凉了一半，除非其它项真的特别优秀，否则基本是无力回天。

那么接下来我们就一起来看看今日一题吧，Let's Go！

题目描述

—————————————————————

给定一个长度为 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

提示：

n == height.length

2 <= n <= 10^5

0 <= height[i] <= 10^4

问题分析

—————————————————————

中等难度题目，肯定不能O(n^2)暴力解决。这里必然有规律。

这种求面积，其实有点滑动区域的意思，那我们可以用双指针解决，现在问题的关键，就是怎么滑动指针。

我们来分析下，区域大小由什么决定：

1.两个位置的间隔

2.两个位置对应高度中，那个较小的。

总结成公式，就是：

Math.min(height[left], height[right]) * (right - left);

既然结果受两个高度中的较小值影响，我们可以尝试滑动较小值，比如我们的例子1，一开始left（0号位置）较小，往后面滑动，整体区域变得更大，我们就使用更大的区域作为结果。

那么之前的0号位置，还可能成为最优解吗？

答案是不能的，因为现在right处于目前最右边，这种情况下0号位都没能打过1号位，那么后面也不会有基于0号位的更大值出现了。

想通了这个，那我们两端就可以放心地往中间收拢，两者碰撞之时，就是循环结束之日。

代码实现

—————————————————————

实现代码如下（更多语言可查看github）：

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

总结

—————————————————————

这道题是一个典型的双指针题目，我们来看下，做出这道题的关键是什么？

1. 找出面积公式，这个是第一步，相对比较容易。

2. 找到正确的移动方法，这个需要结合公式推测，需要多练习。

好了，今天的题解到此结束，大家可以评论区留言讨论

<END>

程序员专属T恤

商品直购链接 👇

  推荐阅读：