首页 > 编程语言 >LeetCode 11 Container with Most Water 解题思路和python代码

LeetCode 11 Container with Most Water 解题思路和python代码

时间:2024-10-08 15:21:01浏览次数:11  
标签:11 right Container area python max height container left

题目
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:
在这里插入图片描述
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:

Input: height = [1,1]
Output: 1

Constraints:

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

解题思路
我们可以看到这里水的体积多少取决于两边的竖直线中较短的那一条。我们可以使用两个指针,一个指向数组的第一个数,另一个指向数组的第二个数。我们可以计算面积,同时移动两个指针中,指向较短竖直线的那一个。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1
        max_area = 0
        
        while left < right:
        	# Calculate the current area 
            width = right - left
            current_area = min(height[left], height[right]) * width

			# Update max_area if the current one is larger
            max_area = max(max_area, current_area)

			# Move the pointer that points to the shorter line
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max_area
        

Time Complexity 是 O(n)
Space Complexity 是 O(1)

标签:11,right,Container,area,python,max,height,container,left
From: https://blog.csdn.net/weixin_57266891/article/details/142737653

相关文章

  • LeetCode 209 Minimum Size Subarray Sum 题目解析和python代码
    题目:Givenanarrayofpositiveintegersnumsandapositiveintegertarget,returntheminimallengthofasubarraywhosesumisgreaterthanorequaltotarget.Ifthereisnosuchsubarray,return0instead.Example1:Input:target=7,nums=[2,3,......
  • 【Python Matplotlib 教程】第23课时-Matplotlib 等高线图
    Matplotlib等高线图等高线图(有时称为水平面图)是一种将三维表面绘制在二维平面上的方法。它在y轴上绘制了两个预测变量X和Y,而响应变量Z则以等高线的形式呈现。这些等高线有时被称为z-切片或等响应值。如果您想观察变量Z随着两个输入变量X和Y的变化情况,使得Z=f(X,Y),则等高线图......
  • 基于Python+Scrapy的高校岗位招聘和分析平台(源码+vue+hadoop+hive+部署文档+可视化大
    收藏关注不迷路!!......
  • python基于深度学习的短视频内容理解与推荐系统(源码+vue+hadoop+hive+部署文档+可视
    收藏关注不迷路!!......
  • 20 基于STM32的温度、电流、电压检测proteus仿真系统(OLED、DHT11、继电器、电机)
    目录一、主要功能二、硬件资源三、程序编程四、实现现象一、主要功能基于STM32F103C8T6采用DHT11读取温度、滑动变阻器模拟读取电流、电压。通过OLED屏幕显示,设置电流阈值为80,电流小阈值为50,电压阈值为60,温度阈值为30随便哪个超过预祝,则继电器切断,LED灯灭掉,若电流......
  • Python精选200Tips:186-190
    针对序列(时间、文本)数据的网络结构续P186--双向LSTM(BidirectionalLongShort-TermMemory2005)(1)模型结构说明(2)创新性说明(3)示例代码:IMDB电影评论情感分析P187--变换器结构(Transformer2017)(1)模型结构说明(2)创新性说明(3)示例代码:模拟气象数据预测(多输出多输出)P188--......
  • 彻底搞懂【Python】切片操作
    在利用Python解决各种实际问题的过程中,经常会遇到从某个对象中抽取部分值的情况,切片操作正是专门用于完成这一操作的有力武器。理论上而言,只要条件表达式得当,可以通过单次或多次切片操作实现任意切取目标值。切片操作的基本语法比较简单,但如果不彻底搞清楚内在逻辑,也极容易产生......
  • Python 格式化输出的高级技巧与应用
    在Python中,格式化输出是一种非常有用的技术,它可以让我们以更清晰、更易读的方式展示数据。以下是一些关于Python格式化输出的高级技巧和代码示例: 使用占位符进行格式化name = "Alice"age = 25print("My name is %s and I am %d years old." % (name, ......
  • Python 代理模式:控制对象访问的智能中介
    在Python编程中,代理模式(ProxyPattern)是一种非常有用的设计模式,它在许多场景下能够为我们提供更加灵活和可控的对象访问方式。代理模式就像是一个中间人,它站在客户端和真实对象之间,代替真实对象处理请求,并且可以在这个过程中添加额外的逻辑,如权限验证、懒加载等。本文将深......
  • Python 享元模式:高效利用内存的设计模式
    在Python编程中,随着程序规模的增大和数据量的增加,内存管理变得至关重要。享元模式(FlyweightPattern)作为一种结构型设计模式,为我们提供了一种在某些场景下有效管理内存、提高系统性能的方法。本文将深入探讨Python中的享元模式,包括其概念、关键要点、实现方式、应用场景......