本文主要是介绍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. 盛最多水的容器【贪心 数组 双指针】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
