本文主要是介绍盛水最多的容器 ---- 双指针，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
题目:
分析:
- 最大容积 即使就是最大面积, 长为下标之差, 宽为两下标对应值的最小值
- 解法一: 暴力枚举: 将每两个数之间的面积都求出来, 找最大值, 时间复杂度较高
- 解法二:
- 假设我们的数组是[6, 2, 5, 4], 我们先假设最左边和最右边, 即6 和 4 之间是最大面积长a*宽b
- 此时我们拿较小的那个数也就是4, 继续和中间的数进行比较
- 如果遇到的是2, 即比4小的数, 那么a在减小, b也在减小, 面积肯定比刚才小, 所以不需要考虑2 和 4 了
- 如果遇到的是5, 即比4大的数, 此时a减小, 而b是不变的(宽还是4), 所以面积还是比原来小
- 得出结论: 找到最左边和最右边的数的最小值, 那么拿着这个最小值和中间的任何一个数相比, 都没有原来的面积大, 所以我们要拿着最大值, 继续比较下去, 并比较面积, 记录下最大的面积
思路:
- 在左右各定义两个变量 left 和right, 计算此时的面积, 存放在max变量中, 这个变量存放最大面积
- 若left指向的是较小的值, 则left++, 并比较此时的面积与max, 如果大于max,则把此时的值给max, 若right指向的是较小的值, 则right-- ,并比较此时的面积与max, 如果大于max,则把此时的值给max
- 直到两指针相遇, 遍历完全部元素, max中存放的就是最大面积
代码:
class Solution {public int maxArea(int[] height) {int left = 0;int right = height.length-1;int max = 0;while(left < right){int min = Math.min(height[left],height[right]);int area = (right - left) * min;max = Math.max(max,area);if(min == height[left]){left++;}else{right--;}}return max;}
}这篇关于盛水最多的容器 ---- 双指针的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
