1. 问题
给定 n 个非负整数 a1,a2,...,an, 每个数代表坐标中的一个点?(i,?ai) . 在坐标内画 n 条垂直线, 垂直线 i? 的两个端点分别为?(i,?ai) 和 (i, 0). 找出其中的两条线, 使得它们与? x? 轴共同构成的容器可以容纳最多的水.
说明: 你不能倾斜容器, 且? n? 的值至少为 2.
- Input: [1,8,6,2,5,4,8,3,7]
- Output: 49
2. 思路
1. 暴力法
暴力解决, 不解释
时间复杂度为 O(n^2), 空间复杂度为 O(1)
2. 双指针法
在数组的 0 位置和 length-1 位置定义一个指针标记, 计算这两个节点的 "容量", 并且设置为最初的最大值 max.
要想扩大容量, 就要减少长度, 增加高度, 那么要 left 标记向前推还是 right 标记向后退呢? 当然是哪个更小搞哪个. 因为如果搞大的, 那么容量不可能变大.
当 left==right 时退出循环, 返回 max.
时间复杂度 O(n), 空间复杂度 O(1)
3. 题解
- class Solution {
- public int maxArea(int[] height) {
- int left=0;
- int right=height.length-1;
- int max=(right-left)*Math.min(height[left],height[right]);
- int newmax=0;
- int i=0;// 没什么实际意义, 只是为了让 line 9 是语句, 避免编译器报错
- while(left!=right){
- i=height[left]<height[right]?left++:right--;
- newmax=(right-left)*Math.min(height[left],height[right]);
- max=newmax>max?newmax:max;
- }
- return max;
- }
- }
[leetcode] 11 - 盛最多水的容器
来源: http://www.bubuko.com/infodetail-3234551.html