【Hot100算法刷题集】双指针-02-盛水最多的容器（含暴力枚举、双指针法及其合理性证明）

🏠关于专栏：专栏用于记录LeetCode中Hot100专题的所有题目
🎯每日努力一点点，技术变化看得见

题目转载

题目描述

🔒link->题目跳转链接
给定一个长度为 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$

解题思路及代码

暴力枚举法

既然要求两条线构成的最大容积，那就计算这些线两两构成的容积大小，以得到最大的容积。这个方法只需要两层for循环即可，算法复杂度为$O(N^2)$。但这个算法的时间复杂度过高，最终会导致超时。

💡tips：这里计算容积时，使用的是高度×底部宽度。容器的高度取决于所有高度中较小的那一个。

class Solution {
public:int maxArea(vector<int>& height) {int maxCap = 0;for(int i = 0; i < height.size(); i++){for(int j = i + 1; j < height.size(); j++){int capacity = min(height[i], height[j]) * (j - i);maxCap = max(maxCap, capacity);}}return maxCap;}
};

双指针法

若定义两个变量left=0，right=height.size()-1，则可以得到由最左和最右两条线所构成的容积，即min(height[left], height[right]) * (right - left)。不管是left或right向内移动一格，宽度均会变小，故此时应当让height[left]和height[right]中小的那一个向内移动，因为宽度减小需要高度增加来补充；而当前高度受限于height[left]和height[right]中小的那一个，若小的线不发生改变，而缩小宽度，则容积只会变小；故每次只要将小的那一边向内移动即可。

下面通过示例1：[1,8,6,2,5,4,8,3,7]执行过程图，演示上述算法描述：

class Solution {
public:int maxArea(vector<int>& height) {int maxCap = 0;int left = 0, right = height.size() - 1;while(left < right){int capacity = min(height[left], height[right]) * (right - left);maxCap = max(maxCap, capacity);if(height[left] > height[right]) --right;else ++left;}return maxCap;}
};

刷题使我快乐😭
文章如有错误，请私信或在下方留言😀