大家好，我就是那个在B站讲算法的「华南溜达虎」。
最近字节的秋招也开奖了，今天看到一位同学拿到了字节的ssp，薪资远超自己的预期。本来某中厂给的薪资就已经让楼主有住公司都行的干劲了，这下字节直接碾压之前的offer，而且不是算法岗，就是普通的后端开发，楼主直接宣布秋招结束。这下又能释放几个offer给池子里的同学了，希望大家都能开出满意的offer。
25届秋招已经开始了，我组织了一个秋招群，大家可以交流学习心得、面试经验，分享工作机会，有啥问题也可以在群里咨询。在群里我整理了一百多家已经启动秋招企业的文档，以及投递入口，每天都会更新，大家只要按照这个文档海投就可以了。
大家互帮互助相信一定可以拿下秋招！计算机相关专业的同学可以 点击底部的「阅读原文」 加群。
言归正传，今天我们来分享一道高频面试题「盛最多水的容器」。
题目描述
思路解析
本题可以使用暴力枚举边界的方式来计算最大值，但是时间复杂度为 O(n2)，oj会判定超时。
下面介绍一个使用双索引的解法。
定义索引L为容器的左边界，索引R为容器的右边界。那么区间[L, R]围成的容器的面积可以表示为area = (R - L) * min(height[L], height[R])，这个面积公式对后续的推导过程很关键。
我们知道了面积的计算方式，给定数组height=[1, 8, 6, 2, 5, 4, 8, 3, 7]，初始化索引L = 0，R = height.size - 1。接下来就是要通过移动L，R去寻找区间[L, R]围成的最大的面积。那么L，R要如何移动呢？
假设L = 0，R = 8，height[L] < height[R]。 此时area = (R - L) * min(height[L], height[R]) = (R - L) * height[L] = 8 * 1 = 8。
如果向左移动
R，R = R - 1 = 7，area = (R - L) * min(height[L], height[R]) = (R - L) * height[L]。由于索引R变小了，R - L是一定会变小的，即使height[R]变大，min(height[L], height[R]) = height[L]，短板依旧是height[L]，面积area = (R - L) * height[L] = 7 * 1 = 7会变小。所以移动长板对应的索引R一定会导致面积area变小。如果向右移动
L，L=L+1=1，area = (R - L) * min(height[L], height[R]) =(R - L) * height[R]。由于索引L变大了，R - L是一定会变小的，但是height[L]变长了，min(height[L], height[R]) = height[R]，短板变成了height[R]，area = (R - L) * height[R] = 7 * 7 = 49变大了。所以移动短板对应的索引L面积area有可能变大。
总结一下上面的过程，移动长板的索引导致区间[L, R]围成的面积area一定会变小，移动短板的索引导致区间[L, R]围成的面积area有可能会变大。我们要找的是最大面积，所以移动长板的索引是没有意义的。这样我们就得到了索引的移动策略：
用 max_res保存最大当前最大面积，每次移动短板对应的索引，计算area，更新max_res。
下面我们给出c++和python两种代码实现。
C++代码
class Solution {
public:
int maxArea(vector<int>& height) {
int height_len = height.size();
int L = 0, R = height_len - 1;
int max_area = INT_MIN;
while (L < R) {
//面积计算公式
int area = (R - L)*min(height[L], height[R]);
//更新最大面积
max_area = max(max_area, area);
//移动短板对应的索引
if (height[L] < height[R]) {
++L;
} else {
--R;
}
}
return max_area;
}
};
python代码
class Solution:
def maxArea(self, height: List[int]) -> int:
heightLen = len(height)
L, R = 0, heightLen - 1
maxArea = float('-inf')
while L < R:
# 面积计算公式
area = (R - L) * min(height[L], height[R])
# 更新最大面积
maxArea = max(maxArea, area)
# 移动短板对应的索引
if height[L] < height[R]:
L += 1
else:
R -= 1
return maxArea
复杂度分析
时间复杂度： 整个过程只遍历了一遍数组height，故时间复杂度为O(n)，其中n为数组height的长度。
空间复杂度： 我们只使用了几个整型的变量，故空间复杂度为O(1)。
号外
经常使用leetcode会员的同学可以使用我的优惠通道啦！
https://leetcode.cn/premium/?promoChannel=ldtiger ，年度会员有效期比官网多俩月，季度会员有效期比官网多两个星期，还有专属福利，需要的读者朋友可以找我了解。
今天的分享就到这里，希望大家能有所收获！
