阅
Leetcode每日一题：11. 盛最多水的容器
11. 盛最多水的容器
题目内容
中等
给定一个长度为 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 <= 10^5
- 0 <= height[i] <= 10^4
解题思路
直接全部循环搜索会超时，使用双指针，短板会决定水最高的高度，当左右两个挡板向内移动的时候，移动长板一定会使面积变小，移动短板则不能确定，两指针从左右边缘开始搜索至它们相邻，时间复杂度O(n),空间复杂度O(1)
我的解答
class Solution:
def maxArea(self, height: List[int]) -> int:
final=0
s=0
i=0
j=len(height)-1
while i<j:
s=(j-i)*min(height[i],height[j])
if s>final:
final=s
if height[i]<height[j]:
i=i+1
else:
j=j-1
if i>=j:
break
return final
赏
