【算法题】11. 盛最多水的容器-力扣(LeetCode)

【算法题】11. 盛最多水的容器-力扣(LeetCode)

1.题目

下方是力扣官方题目的地址

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 <= 105
• 0 <= height[i] <= 104

2.题解

思路

这题很容易想到暴力解法，就是利用两个for循环，枚举出所有的情况，维护一个最大值

不过该题有更好的解法：双指针

首先我们初始化双指针：一个在最左边、一个在最右边：

如果哪边短一些，哪边就往中间进一位，维护一个最大值

那么为什么要移动最短的一边呢？

（以下解释并不严谨，主要是有助于更好理解）

面积取决于长（横轴）和宽（纵轴）。在移动的时候，长度必然是减小的，这我们改变不了。

而宽度则取决于我们的指针是如何移动的。而宽度又是由最短边决定的。如果我们移动长边，那么面积必然是减小或者不变的；那如果我们移动短边，由于宽度取决于短边，面积是有可能会变大的。所以我们需要移动短边。

Python代码

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        l,r=0,len(height)-1
        ans=0
        while l<r:
            ans=max(ans,min(height[l],height[r])*abs(l-r))
            if height[l]>height[r]:r-=1
            else:l+=1
        return ans

3.结语

本人资历尚浅，发博客主要是记录与学习，欢迎大佬们批评指教！大家也可以在评论区多多交流，相互学习，共同成长。