Problem:11.盛水最多的容器

题目描述

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

暴力解

两条线i和j之间的盛水量就是面积即min(height[i],height[j]) * (j - i)，两重循环遍历height数组，res变量表示两条线之间的盛水量，表示单个结果，ans表示最大盛水量，这种从全部结果中找到全局最大值的情况我习惯用ans = max(ans,res)来处理。具体代码如下：

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

暴力解采用两重循环，时间复杂度是O(n^2)显然会超时。

💡小Tips：判断什么时间复杂度会超时一般以 $10^8$ 为依据，这里n最大为 $10^5$ 那么n^2最大为 10 ^ 10 > 10^8,因此会超时。

双指针

定义两个指针i 和 j分别指向height数组的两端，双指针一般都是同一时间只移动一个指针，现在我们的问题就是要考虑什么情况下移动哪个指针，然后我们考虑到盛水容量取决于短板和两板之间的长度，而现在我们的指针是从两端向中间移动的，所以我们优化的点只能是短板，只有短板更长才有可能使盛水容量变大，因此只需要让短板那边的指针移动即可，具体代码如下：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n = height.size();
        int ans = 0;
        int i = 0,j = n-1;
			 // 当两个指针未相遇时，持续尝试计算当前区间能盛的最大水量
        while(i < j) {
            int res = min(height[i],height[j]) * (j - i); 
            ans = max(ans,res);
            // 关键策略：移动较短的那一边的指针
        		// 原因：宽度 (j - i) 在缩小，若想获得更大的容量，必须尝试找到更高的“短板”
        		// 如果移动较高的那一边，新的高度不会超过当前短板，容量只会变小或不变
            if(height[i] < height[j]) i++; // 左边是短板，尝试向右寻找更高的左边界
            else j--; // 右边是短板（或相等），尝试向左寻找更高的右边界
        }
        return ans;
    }
};

双指针过程中两个指针总共移动n次，时间复杂度是O(n)

💡另外双指针确定移动指针策略的过程实际也是用到了贪心的思想即局部最优推出全局最优

最后

新人up，如有不足还请多多指正，欢迎交流！
如果内容对你有帮助的话，还请点赞支持一下喽🙏🙏
你的支持是我前进的最大动力！！
up正在更新力扣hot100的题目，有需要的朋友欢迎点赞、收藏加关注哦！