盛水最多的容器
The following article is from 牛牛码特 Author 牛牛码特
二本院校，本科校招进鹅厂，呆过外企，肝过字节，目前回鹅厂担任高级工程师。分享技术，分享踩过的坑以及一些思考。每周不定时更新一篇硬核，码字不易，希望小伙伴们多多一键三连，多和牛牛交流。
来源丨牛牛码特（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;}}
总结
—————————————————————
这道题是一个典型的双指针题目，我们来看下，做出这道题的关键是什么？
找出面积公式，这个是第一步，相对比较容易。
找到正确的移动方法，这个需要结合公式推测，需要多练习。
好了，今天的题解到此结束，大家可以评论区留言讨论
<END>
程序员专属T恤
推荐阅读：
想刷 LeetCode ，在此之前需要做什么准备？
拼命刷题、实习两年，我通过校招进大厂