哈密网站制作公司-哈密网站建设|哈密网络公司|哈密做网站,河北app在线下载,网站需要的栏目,适合中小企业的管理软件题目描述 跳转到leetocde题目 给定一个长度为 n 的整数数组 height 。有 n 条垂线#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明#xff…题目描述 跳转到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 i1; 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;}
}最后成功啦
