大宗商品b2b网站建设2022年新闻大事
题目描述 跳转到leetocde题目
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：不能倾斜容器。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
分析题目
该题目说白了就是求 两元素的间隔*最小元素 的值
- 暴力解法， 双循环该数组
height, 依次比较哪两个数的乘积最大
class Solution {public int maxArea(int[] height) {int max = -1;for(int i = 0; i< height.length - 1; i++){for(int j = i+1; j< height.length; j++){max = (j-i) * Math.min(height[i], height[j]) > max ? (j-i) * Math.min(height[i], height[j]): max;}}return max;}
}
结果 超出时间限制！，回过头来看代码该解法的时间复杂度是O(n的平方)
2. 优化代码
双指针方法：。具体思路是从数组两端开始向中间靠拢，哪一侧的高度低就驱使指针向内移动，直到两指针相遇，期间每次都计算当前区域面积和最大面积比较，取较大值返回即可。
class Solution {public int maxArea(int[] height) {// 双指针方法减少时间复杂度int max = -1;// 定义左右指针int left = 0, right = height.length - 1;// 遍历数组while(left <= right){max = Math.min(height[left], height[right])*(right-left) > max ? Math.min(height[left], height[right]) * (right-left) : max;if(height[left] < height[right]) {left++;}else{right--;}}return max;}
}
最后成功啦！