【刷题笔记4】盛最多水的容器

题目来源LeetCode 11.盛最多水的容器
本贴为个人日常刷题笔记，有任何问题欢迎随时交流~
该题类别是：数组

一、题目

• 给你 n 个非负整数$\{a_1，a_2，...，a_n\}$每个数代表坐标中的一个点 $(i,a_i)$，这里的$i$指的是元素的下标 。在坐标内画$n$条垂直线，垂直线$i$的两个端点分别为$(i,ai)$和$(i,0)$。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

• 说明：你不能倾斜容器。（这个说明挺滑稽的~）

二、提示

• $n=height.length$
• $2\le n\le 3\ast 10^4$
• $0\le height[i]\le 3\ast 10^4$

三、思考

1. 对题目方面的思考

• 非负整数的数组
• 坐标是$(i,a_i)$，是二维的
• 返回的是最大容量
• 本质上$x$和$y$在$[0,n-1]$范围内，找到$(x,a_x)$与$(y,a_y)$，使得$s=|x-y|\ast \min (a_x,a_y)$达到最大
• 是否是动态规划问题？

2. 对官方给出的答案的思考

• 固定高度还是固定宽度（为什么先假设宽度，因为最大宽度是可以确定的）

• 目标是使得$s=|x-y|\ast \min (a_x,a_y)$达到最大值，那么可以先假定$|x-y|$达到最大

  • 即 x = 0, y = len(nums) - 1时可以使得$|x-y|=len(nums)$达到最大
  • 令d = |x - y|，h = min(a_x, a_y)

• 再考虑另一边，即$min(a_x,a_y)$

  • 要想扩大总量 $s$，则需要有$min(a_x,a_y)$的变动大于$|x-y|$的变动的可能

  • 假定x < y：

    • 若a_x < a_y：
      • y向左移动，$min(a_x,a_y^{\prime })\le a_x$，h上限不变而d变小了，s变小
      • x向右移动，$min(a_x^{\prime },a_y)$ 不确定，存在总体变大可能，可以考虑
    • 若a_x > a_y：
      • y向左移动，$min(a_x,a_y^{\prime })$ 不确定，存在总体变大可能，可以考虑
      • x向右移动，$min(a_x^{\prime },a_y)\le a_x$，h上限不变而d变小了，s变小
    • 若a_x = a_y：
      • 若x或y任一个移动后，遇到更大的数，h不变但d变小了，s变小（短板决定）
      • 若x或y任一个移动后，遇到更小的数，h变小且d变小，s变小
      • 因此x和y同时移动才有可能使得s变大
    • 因此若要找打更大的可能，只能移动min(a_x, a_y)对应的x或y，即移动短板

• 时间复杂度：$O(n)$，空间复杂度为$O(1)$

四、解法（贪心算法 + 左右双指针）

• 注意第一种是没考虑到相等的情况下（显然考虑相等的情况可以加快遍历的速度）

class Solution1:
    def maxArea(self, height: List[list]) -> int:
        # 定义双指针
        i = 0
        j = len(height) - 1
        res = (j - i) * min(height[i], height[j])
        while i < j:
            if height[i] >= height[j]:
                j -= 1
            else:
                i += 1
            temp = (j - i) * min(height[i], height[j])
            res = max(temp, res)
        return res


class Solution2:
    def maxArea(self, height: List[int]) -> int:
        i = 0
        j = len(height) - 1
        res = j * min(height[i], height[j])
        while i < j:
            temp = (j - i) * min(height[i], height[j])
            res = max(temp, res)
            if height[j] > height[i]:
                i += 1
            elif height[j] < height[i]:
                j -= 1
            else:
                i += 1
                j -= 1
        return res