题目描述
思路:左右指针
方法一:暴力,超出时间限制
模拟所有情况,记录最大的体积值。
体积 = 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)
方法二:双指针
思路:
- 初始化:双指针left和right分别位于水槽左右两端;
- 循环收窄: 直至双指针相遇时跳出;
- 更新面积最大值:res;
- 选定两板高度中的短板,向中间收窄一格;
- 返回值:返回面积最大值res即可;
木桶容量由短板决定, 移动长板的话, 水面高度不可能再上升, 而宽度变小了, 所以只有通过移动短板, 才有可能使水位上升.
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int res = 0;
while (left < right) {
int w = right - left;
int h = Math.min(height[left], height[right]);
res = Math.max(res, w * h);
if (height[left] < height[right]) {
left ++;
} else {
right --;
}
}
return res;
}
}
标签:right,int,res,height,LeetCode11,最多水,left,Math,刷题
From: https://www.cnblogs.com/keyongkang/p/17963840