11. [M] Container With Most Water

https://leetcode.com/problems/container-with-most-water/

暴力搜索

最简单直接暴力的方案,时间复杂度 O(n^2),空间复杂度 O(1)。

// 388 ms
class Solution {
public int maxArea(int[] height) {
int max = 0;
for (int i = 0; i < height.length - 1; i++) {
for (int j = 1; j < height.length; j++) {
int capacity = (j - i) * Math.min(height[i], height[j]);
max = capacity > max ? capacity : max;
}
}
return max;
}
}

第一步优化,内部循环 j 无需从 1 开始,可从 i + 1 开始

// 205 ms
class Solution {
public int maxArea(int[] height) {
int max = 0;
for (int i = 0; i < height.length - 1; i++) {
for (int j = i + 1; j < height.length; j++) {
int capacity = (j - i) * Math.min(height[i], height[j]);
max = capacity > max ? capacity : max;
}
}
return max;
}
}

第二步优化,外层循环只需计算比之前高的柱子。由于越往后容器越窄,因此比之前低的柱子围起来的水量一定是更少的。

// 126 ms
class Solution {
public int maxArea(int[] height) {
int max = 0;
int lastMaxHeight = 0;
for (int i = 0; i < height.length - 1; i++) {
if (height[i] > lastMaxHeight) {
lastMaxHeight = height[i];
for (int j = i + 1; j < height.length; j++) {
int capacity = (j - i) * Math.min(height[i], height[j]);
max = capacity > max ? capacity : max;
}
}
}
return max;
}
}

两侧夹逼

从两侧夹逼,每次从高度比较低的一侧向中心移动。时间复杂度 O(n),空间复杂度 O(1)。

原理是:面积取决取宽度和高度。先取最大宽度,那么当宽度变小的时候,只有尽量取高点,才能保证面积最大。因此每次向中心移动的时候,都保留高点,移动较低点。

// 2ms
class Solution {
public int maxArea(int[] height) {
int max = 0;
for (int i = 0, j = height.length - 1; i < j; ) {
int t = Math.min(height[i], height[j]) * (j-i);
max = t > max ? t : max;
t = height[i] > height[j] ? j-- : i++;
}
return max;
}
}