题目描述
方法一：暴力，超出时间限制
模拟所有情况，记录最大的体积值。
体积 = Math.min(height[i], height[j]) * (j - i)
class Solution {
public int maxArea(int[] height) {
int res = Integer.MIN_VALUE;
for (int i = 0; i < height.length; i ++) {
for (int j = i + 1; j < height.length; j ++) {
int edge = Math.min(height[i], height[j]);
res = Math.max(res, (j - i) * edge);
}
}
return res;
}
}
时间复杂度O(n2)
方法二：双指针
思路：
- 初始化： 双指针 iii , jjj 分列水槽左右两端；
- 循环收窄： 直至双指针相遇时跳出；
- 更新面积最大值：res；
- 选定两板高度中的短板，向中间收窄一格；
- 返回值：返回面积最大值res即可；
木桶容量由短板决定, 移动长板的话, 水面高度不可能再上升, 而宽度变小了, 所以只有通过移动短板, 才有可能使水位上升.
class Solution {
public int maxArea(int[] height) {
int i = 0, j = height.length - 1;
int res = Integer.MIN_VALUE;
while (i <= j) {
int area = (j - i) * Math.min(height[i], height[j]);
if (area > res) {
res = area;
}
if (height[i] <= height[j]) {
i ++;
}else if (height[i] > height[j]) {
j --;
}
}
return res;
}
}