当前位置:   article > 正文

LeetCode 第11题:盛最多水的容器(Python3解法)_盛水最多的容器题解python

盛水最多的容器题解python

1:问题描述

来源:LeetCode

难度中等


问题详情:
给定一个长度为 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


2:问题分析

2.1 时间复杂度和空间复杂度

在真正开始介绍各种算法前,先以表格形式展示各自的时间复杂度和空间复杂度,其中 N N N表示列表 h e i g h t height height的长度。

算法时间复杂度空间复杂度
双指针 O ( N ) O(N) O(N) O ( 1 ) O(1) O(1)

2.2 双指针

2.2.1 流程

  1. 首先初始化一个头指针和尾指针分别指向数组的最左边和最右边,并且赋值最大面积 m a x _ a r e a = 0 max\_area=0 max_area=0
  2. 计算当前面积,计算面积的公式为:
    a r e a = ( t a i l − h e a d ) × m i n ( h e i g h t [ t a i l ] , h e i g h t [ h e a d ] ) area =(tail-head)×min(height[tail],height[head]) area=(tailhead)×min(height[tail],height[head])
  3. 更新当前的最大面积
    m a x _ a r e a = m a x ( m a x _ a r e a , a r e a ) max\_area=max(max\_area,area) max_area=max(max_area,area)
  4. 比较头尾指针指向的数值大小
  5. 将较小者指针向中间移动
  6. 重复上述步骤直至头尾指针指向同一位置
  7. 输出最大面积

2.2.2 原理

为什么上述流程能够找到最优解呢?
接下来就证明这种方案的合理性。

首先假设头尾指针相距为 t t t,并且假设 h e i g h t [ h e a d ] < h e i g h t [ t a i l ] height[head]<height[tail] height[head]<height[tail],则面积
a r e a = t × h e i g h t [ h e a d ] area=t×height[head] area=t×height[head]
假设移动最大者,那么 t 2 = t − 1 < t t_2=t-1<t t2=t1<t,因为高取决于两边的最短边,因此
因此新的高 h t 2 h_{t_2} ht2必然是 ≤ h e i g h t [ h e a d ] ≤height[head] height[head]的,所以新的面积
a r e a 2 = t 2 × h t 2 ≤ a r e a area_2=t_2×h_{t_2}≤area area2=t2×ht2area.
所以可以看出,移动两者中的最长者必然会导致面积变小;同时也可以进一步想到,无论这个尾指针怎么往内部移动,都不会找到一个更大面积的情况。

也就是说以这个最左边为一边的除了当前 a r e a area area这个情况外的其它情况都不可能是最优解。

所以我们需要记录当前的面积,并移动最左边的指针。

也就是移动最长边必然会导致更小或者不变,移动最短边则有可能会变好。

通过不断的这样筛选的过程,我们其实仍然是遍历了所有可能,只不过那些被淘汰的是隐式地。

2.2.3 代码

def myAtoi(s: str) -> int:
    n = len(height)
    head = 0
    tail = n - 1

    # 分别对比左右指针指向的数,最大的一方指针保持不懂,另一方向中间移动
    max_area = 0
    while head != tail:
        if height[head] > height[tail]:
            area = (tail - head) * height[tail]
            tail -= 1
        else:
            area = (tail - head) * height[head]
            head += 1

        max_area = max(max_area, area)

    return max_area
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

对于时间复杂度,因为首尾指针合在一起指向了所有数组的数,所有时间复杂度为 O ( N ) O(N) O(N)

空间复杂度, O ( 1 ) O(1) O(1)

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小蓝xlanll/article/detail/146370
推荐阅读
相关标签
  

闽ICP备14008679号