双指针力扣hot100盛最多水的容器以及寒假展望

2024 1.3

终于A了一道，却让我输的这么彻底。待我娓娓道来。

首先题目，

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

我的想法，暴力，从头开始一个一个构建容器得到最优选择。结果爆了，过了54个样例，之后超出时间限制了。没办法只能另谋他法。

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

双指针法，官方题解。

模拟过程：

在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度 ?1-1?1? 变短：

若向内 移动短板 ，水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j]) 可能变大，因此下个水槽的面积 可能增大 。
若向内 移动长板 ，水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j])? 不变或变小，因此下个水槽的面积 一定变小 。
因此，初始化双指针分列水槽左右两端，循环每轮将短板向内移动一格，并更新面积最大值，直到两指针相遇时跳出；即可获得最大面积。

算法流程：
初始化： 双指针 iii , jjj 分列水槽左右两端；
循环收窄： 直至双指针相遇时跳出；
更新面积最大值 resresres ；
选定两板高度中的短板，向中间收窄一格；
返回值： 返回面积最大值 resresres 即可；

作者：Krahets
链接：https://leetcode.cn/problems/container-with-most-water/solutions/11491/container-with-most-water-shuang-zhi-zhen-fa-yi-do/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

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

作者：力扣官方题解
链接：https://leetcode.cn/problems/container-with-most-water/solutions/207215/sheng-zui-duo-shui-de-rong-qi-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

写在最后

? 最近的日期不是很赶巧，周末要交课程大作业，15号之前要交毕设开题报告。10号据说要安排华子的上机考试，以个人力扣的进度水平来看感觉很难过吧，尽力就好。之后白天的话2号以来一直在学渗透工程的课程，涉及了一些基础，虚拟机配置啊，工具套件啊，代理以及简单前端HTML等内容，由于本人网络基础尚可，网络基础的课直接跳过了，继续努力吧。晚上感觉力扣刷的太干了，在学长的建议下买了本代码的书看看什么感觉，之后考研复试的书籍还没到自己也没开始学，等复试班出了再学吧。