LeetCode50天刷题计划（Day 8—— 盛最多水的容器（23.00-1.20）

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

今天这题很有意思

一、题目

盛最多水的容器

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

二、思路

一上去第一反应动态规划，写了一半写不下去了
然后开始暴破， python时间超限，c++估计可以
然后学习了双指针，以下介绍此思路：

一般需要移动左右两头的问题可以考虑双指针，题目的难点在于如何移动两个指针。
根据题目中定义的盛水面积的计算方式，可以发现两个特点：一是在相同情况下，两边距离越远越好，二是区域受限于较短边的长度。
在暴力解中，我们固定了左指针，向右移动右指针，在每次移动中同时改变了矩形的长度和宽度，导致每次都需要重新计算面积。那么我们可否依据盛水面积的两个特点加速剔除一些没有必要的计算呢？

首先，如果使右指针从最右向左扫描，当左边的柱子比右边短的时候，就可以跳过这个计算，因为宽度和高度如果同时减少，面积一定会更小；（根据这个可以进一步优化暴破解法，左指针不动，右指针从右向左遍历）
其次，如果左右指针同时向中间移动，应该先移动较短的指针，因为只有将短者变长才有可能用高度弥补减少的宽度，移动长指针只会使最小高度不变（新指针大于原小指针）或变小（新指针小于原小指针），面积只会更小。

双指针算法的流程如下：左右指针分别从两头出发向中间移动，每次固定较长的边，短边指针向内移动，计算该边变长情况下的面积，同时决定是否交换移动顺序。

三、代码

1.暴破：左指针不动，右指针左向右遍历（python，时间超限）

class Solution:
    def maxArea(self, height: List[int]) -> int:
        #遍历，i是左边界，j是右边界
        max_water=0
        for i in range(1,len(height)):
            for j in range(i+1,len(height)+1):
                #求出这种情况下的水量
                cur_water=(j-i)*min(height[i-1],height[j-1])
                if(cur_water>max_water):
                    #保留最大水量
                    max_water=cur_water
        return max_water

2.优化暴破：左指针不动，右指针右向左遍历（python,有一个bt测试点还是没过）

class Solution:
    def maxArea(self, height: List[int]) -> int:
        #遍历，i是左边界，j是右边界
        max_water=0
        n=len(height)
        for i in range(1,n):
            #如果左边比右面最后一个低，移动右面没作用，一次性计算完此时面积直接break
            if(height[i-1]<=height[-1]):
                cur_water=(n-i)*min(height[i-1],height[-1])
                if(cur_water>max_water):
                    #保留最大水量
                    max_water=cur_water
                continue;
            #否则，移动右指针，记录上次计算面积时右边的最大高度
            right_height=0
            for j in range(len(height),i,-1):
                #如果有可能更高
                if(height[j-1]>right_height):
                    right_height=height[j-1]
                    cur_water=(j-i)*min(height[i-1],height[j-1])
                    if(cur_water>max_water):
                        #保留最大水量
                        max_water=cur_water
        return max_water

3.双指针（python，太优雅了）

class Solution:
    def maxArea(self, height: list[int]) -> int:
        left=0 #左指针指向最左，
        right=len(height)-1 #右指针指向最右
        max_area=0 #最大面积

        #当左右指针不相逢
        while(left<right):
            #计算当前面积
            cur_area=(right-left)*min(height[left],height[right])
            if(cur_area>max_area):
                max_area=cur_area
           
            #移动指针
            if(height[left]<=height[right]):#左指针右移
                temp=left
                while(temp<right and height[temp]<=height[left]):
                    temp+=1
                left=temp
            else:#右指针左移
                temp=right
                while(temp>left and height[temp]<=height[right]):
                    temp-=1
                right=temp
        return max_area