LeetCode-11. 盛最多水的容器【贪心 数组 双指针】

2024-03-31 20:28

本文主要是介绍LeetCode-11. 盛最多水的容器【贪心 数组 双指针】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

LeetCode-11. 盛最多水的容器【贪心 数组 双指针】

  • 题目描述:
  • 解题思路一:看提示知道是用贪心和双指针解法。贪心问题一般都比较难以想到。求面积肯定是希望底边(right - left)先越大越好,所以初始化left, right = 0, len(height) - 1。然后我们要求的是宽度w 乘以 两个柱子中最短的柱子h,此时我们若移动比较高的柱子,结果只有两种:1.比最短的柱子h 依然高,此时无论这个柱子再高,得到的结果都是h,因为我们要的是最短的,所以不仅宽度w减少了,高度h还没变,结果肯定变小,这是不符合的. 2.比最短的柱子h 矮了,此时h变得更小了,w也减小,就更不可能了。 所以只有移动短的柱子才有可能比原来的结果大,因为虽然宽度w在减小,但可能h变大,w*h整体才有可能变大。h变小的话可能整体变小,但不影响,因为我们已经记录下了最大值了。所以综上只能移动短的柱子.
  • 解题思路二:
  • 解题思路三:

题目描述:

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

解题思路一:看提示知道是用贪心和双指针解法。贪心问题一般都比较难以想到。求面积肯定是希望底边(right - left)先越大越好,所以初始化left, right = 0, len(height) - 1。然后我们要求的是宽度w 乘以 两个柱子中最短的柱子h,此时我们若移动比较高的柱子,结果只有两种:1.比最短的柱子h 依然高,此时无论这个柱子再高,得到的结果都是h,因为我们要的是最短的,所以不仅宽度w减少了,高度h还没变,结果肯定变小,这是不符合的. 2.比最短的柱子h 矮了,此时h变得更小了,w也减小,就更不可能了。 所以只有移动短的柱子才有可能比原来的结果大,因为虽然宽度w在减小,但可能h变大,w*h整体才有可能变大。h变小的话可能整体变小,但不影响,因为我们已经记录下了最大值了。所以综上只能移动短的柱子.

class Solution:def maxArea(self, height: List[int]) -> int:left, right, result = 0, len(height) - 1, 0while left < right:if height[left] < height[right]:result = max(result, height[left] * (right - left))left += 1else:result = max(result, height[right] * (right - left))right -= 1return result 

时间复杂度:O(n)
空间复杂度:O(1)

解题思路二:


时间复杂度:O(n)
空间复杂度:O(n)

解题思路三:


时间复杂度:O(n)
空间复杂度:O(n)

这篇关于LeetCode-11. 盛最多水的容器【贪心 数组 双指针】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/865261

相关文章

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

Java Optional避免空指针异常的实现

《JavaOptional避免空指针异常的实现》空指针异常一直是困扰开发者的常见问题之一,本文主要介绍了JavaOptional避免空指针异常的实现,帮助开发者编写更健壮、可读性更高的代码,减少因... 目录一、Optional 概述二、Optional 的创建三、Optional 的常用方法四、Optio

如何将Tomcat容器替换为Jetty容器

《如何将Tomcat容器替换为Jetty容器》:本文主要介绍如何将Tomcat容器替换为Jetty容器问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Tomcat容器替换为Jetty容器修改Maven依赖配置文件调整(可选)重新构建和运行总结Tomcat容器替

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

Python容器类型之列表/字典/元组/集合方式

《Python容器类型之列表/字典/元组/集合方式》:本文主要介绍Python容器类型之列表/字典/元组/集合方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 列表(List) - 有序可变序列1.1 基本特性1.2 核心操作1.3 应用场景2. 字典(D

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

解决java.lang.NullPointerException问题(空指针异常)

《解决java.lang.NullPointerException问题(空指针异常)》本文详细介绍了Java中的NullPointerException异常及其常见原因,包括对象引用为null、数组元... 目录Java.lang.NullPointerException(空指针异常)NullPointer

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::