中英文建设网站,网站建设swot市场分析,建设网站后期人员薪酬,做树状图的网站LeetCode11. 盛最多水的容器题解
题目链接#xff1a;
https://leetcode.cn/problems/container-with-most-water
示例 思路
暴力解法
定住一个柱子不动#xff0c;然后用其他柱子与其围住面积#xff0c;取最大值。
代码如下#xff1a;
public int maxArea1(int[]…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 Maxresultleft和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;}
}
