LeetCode11☞盛最多的雨水

关联LeetCode题号11

本题特点

• 双指针方法解题
• 盛雨水的面积最大的情况，长方形两侧高度的最小值即min(height[start+1], height[end-1])
• 第i条线实际上是 start+1 start计数从0开始
• start，end 不能同时移动，因height[start+1] ，height[end-1]大小决定， height[start+1]大 说明同样大小的end-(start+1) 最大面积 要舍弃height[end-1] 所以 end-=1 ,start+=1 同理就是height[start+1] 小

本题思路

1. left，right分别在数组两侧
2. 通过比较height[start+1] ，height[end-1]决定end-=1 还是start+=1
3. 双指针的时间复杂度O(N)

class Solution:def maxArea(self, height: List[int]) -> int:maxArea = float('-inf')start = 0end = len(height)while start < end:tmp = (end - (start + 1)) * min(height[start], height[end-1])maxArea = max(tmp, maxArea)if height[start] < height[end-1]:start += 1else:end -= 1return maxArea

Java实现

public class ContainerWithMostWater_11 {public int maxArea(int[] height) {int left = 0;int right = height.length-1;int maxArea = 0;while(left < right){int tmpArea = (right - left) * Math.min(height[left], height[right]);maxArea = Math.max(tmpArea, maxArea);if (height[left] < height[right]){left ++;}else{right --;}}return maxArea;}@Testpublic void TestContainerWithMostWater(){int[] height = {1,8,6,2,5,4,8,3,7};System.out.println(maxArea(height));}
}