当前位置：首页 > article >正文

每日一题：LeetCode-11.盛水最多的容器

article 2024/9/25 14:40:23

每日一题系列（day 13）

前言：

🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈

🔎🔎如果说代码有灵魂，那么它的灵魂一定是👉👉算法👈👈，因此，想要写出💚优美的程序💚，核心算法是必不可少的，少年，你渴望力量吗😆😆，想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇，我们要做的，就是斩妖除魔💥💥，打怪升级！💪💪当然切记不可😈走火入魔😈，每日打怪，拾取经验，终能成圣🙏🙏！开启我们今天的斩妖之旅吧！✈️✈️

题目：

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。

示例：

在这里插入图片描述

提示：

n == height.length
2 <= n <= 105
0 <= height[i] <= 104
说明：你不能倾斜容器。

思路：

首先，我们可以使用暴力解法，两层for循环枚举所有情况，枚举完所有情况将最大的值返回即可。
但是我们的暴力解法时间复杂度是比较高的，对于这题来说，暴力解法应该是不能通过的，有兴趣的小伙伴可以自己尝试。

我们观察示例，其实不难看出，这题我们可以使用双指针来解决：双指针解决的问题：
1、首先，我们可以先设置两个指针left，right，一个指向数组的首元素下标，一个指向数组，我们在设置一个max变量，用来记录容器的最大体积。
2、我们按照题目，设置一个局部变量v用来表示当前体积，然后比较当前体积v与最大体积max，返回两个数中的较大值。
3、接着，如果左指针指向的值小于右指针指向的值，那么就将左指针右移，反之我们将右指针左移。
4、有人可能会问，这样遍历的方式并不会将所有的情况枚举出来，那么还能保证正确性吗？举个例子，我们最开始的时候，左边和最右边可以得到一个体积v，而如果让比较小的那个指针向两指针区间枚举，这个得到的体积一定是小于原有的v的，同理，右指针也是如此：
5、接下来我们就一直进行循环即可，最后得到的max值就是最大的蓄水池体积。

在这里插入图片描述

代码实现：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1, ret = 0;//ret为最大的体积
        while(left < right)//两指针相遇即结束
        {
            int v = min(height[left], height[right]) * (right - left);//将本次的体积算出来
            ret = max(v, ret);//与之前保存的最大体积比较，如果大于最大体积则刷新ret，否则ret不变

            if(height[left] < height[right]) left++;//哪个指针较小我们就移动哪个指针
            else right--;
        }
        return ret;//最后返回最大体积即可
    }
};