LeetCode11. 盛最多水的容器题解
题目链接:
https://leetcode.cn/problems/container-with-most-water
示例
思路
暴力解法
定住一个柱子不动,然后用其他柱子与其围住面积,取最大值。
代码如下:
public int maxArea1(int[] height) {
int n = height.length;
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int area = Math.min(height[i], height[j]) * (j - i);
ans = Math.max(ans, area);
}
}
return ans;
}
此方法的时间复杂度为O(n^2),很显然太慢。我们需要想其他的思路。
对撞指针
暴力解法的搜索空间如下
那么我们是否可以缩小搜索空间呢?
以第一行为例,高度限制为1了,那么我们只需要看宽度最大的地方即可,第一行搜索空间中所有灰色的都不用看了;
以第二行为例,我们不止要看宽度最大的地方,因为height[right]会变大,所以我们只需要看第二行图中三个即可。
以此类推;
我们定义:
left为数组开始位置;
right为数组结束位置;
初始化所求最大面积为result = 0;
- 计算result = Max(result,left和right之间围成的面积);
- 如果height[left] <= height[right]:left++;
- 如果height[left] > height[right]:right--;
- 直到left > right;
代码如下
class Solution {
public int maxArea(int[] height) {
if (height == null || height.length <= 1) return 0;
int left = 0, right = height.length - 1;
int result = 0;
while (left < right) {
//计算面积
result = Math.max(result, Math.min(height[left], height[right]) * (right - left));
if (height[left] <= height[right]) {
left++;
} else {
right--;
}
}
return result;
}
}
标签:right,int,题解,height,LeetCode11,ans,最多水,left
From: https://www.cnblogs.com/nicaicai/p/18264826