https://leetcode-cn.com/problems/container-with-most-water/
参考题解，暴力法
直接两重循环，遍历左右两根柱子的所有组合情况。因为两重循环，所以时间复杂度为 O(n^2)。 因为没有而外开辟空间，所以空间复杂度为 O(1)。
Python 的代码会超出时间限制，Rust 和 Golang 这种需要编译的代码可以过，不过速度比较慢。
Python 代码
class Solution:
def maxArea(self, height: List[int]) -> int:
result = 0
for i in range(len(height)-1):
for j in range(i + 1, len(height)):
curHeight = min(height[i], height[j])
curWdith = j - i
curArea = curWdith * curHeight
result = max(result, curArea)
return result
JavaScript 代码
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let result = 0;
for (let i = 0; i < height.length; i += 1) {
for (let j = i + 1; j < height.length; j += 1) {
const curWidth = j - i;
const curHeight = Math.min(height[i], height[j]);
const curArea = curWidth * curHeight;
if (curArea > result) {
result = curArea;
}
}
}
return result;
};
Rust 代码
impl Solution {
pub fn max_area(height: Vec<i32>) -> i32 {
let mut result = i32::min_value();
for i in 0..(height.len() - 1) {
for j in (i + 1)..(height.len()) {
result = i32::max(result, i32::min(height[i], height[j]) * (j - i) as i32);
}
}
result
}
}
Golang 代码
func maxArea(height []int) int {
result := 0
for i := 0; i < len(height)-1; i++ {
for j := i + 1; j < len(height); j++ {
curArea := 0
if height[i] < height[j] {
curArea = height[i] * (j - i)
} else {
curArea = height[j] * (j - i)
}
if curArea > result {
result = curArea
}
}
}
return result
}
C++ 代码
class Solution {
public:
int maxArea(vector<int>& height) {
int result = 0;
for (int i = 0; i < height.size() - 1; i++) {
for (int j = 0; j < height.size(); j++) {
int curHeight = min(height[i], height[j]);
int curWidth = j - i;
int curArea = curHeight * curWidth;
result = max(result, curArea);
}
}
return result;
}
};
参考题解，双指针两头夹逼
这方法不是很好理解，建议先看看代码，再回来看分析。
我这里提供一个思路：我们把数组最左边的柱子叫做 a，最右边的柱子叫做 b。 假设 a 的高度小于 b。同时在 a 和 b 之间存在着一根柱子 c。
- 情况1：c <= a。这种情况 a 和 c 构成的面积一定小于 a 和 b 构成的面积。
- 情况2：a < c <= b。这种情况 a 和 c 构成的面积也一定小于 a 和 b 构成的面积。
- 情况3：b < c。这种情况 a 和 c 构成的面积还是一定小于 a 和 b 构成的面积。
上面 3 种情况，大家自己画个图就清楚了。 你会发现无论 c 是多高的。a 和 c 的面积都不可能超过 a 和 b 的面积， 也就是说柱子 a 和 ab 之间的任意一根柱子都没有必要判断了。
Python 代码
class Solution:
def maxArea(self, height: List[int]) -> int:
result, left, right = 0, 0, len(height)-1
while left < right:
curHeight = min(height[left], height[right])
curWdith = right - left
curArea = curWdith * curHeight
result = max(result, curArea)
if height[left] < height[right]: left += 1
else: right -= 1
return result
JavaScript 代码
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function(height) {
let result = 0;
let left = 0;
let right = height.length - 1;
while (left < right) {
let curWidth = right - left;
let curHeight = Math.min(height[left], height[right]);
let curArea = curWidth * curHeight;
if (curArea > result) {
result = curArea;
}
if (height[left] < height[right]) {
left += 1;
} else {
right -= 1;
}
}
return result;
};
Rust 代码
impl Solution {
pub fn max_area(height: Vec<i32>) -> i32 {
let mut left = 0;
let mut right = height.len() - 1;
let mut result = 0;
while left < right {
let cur_height = std::cmp::min(height[left], height[right]);
let cur_width = (right - left) as i32;
let cur_area = cur_height * cur_width;
result = std::cmp::max(result, cur_area);
if height[left] < height[right] {
left += 1;
} else {
right -= 1;
}
}
result
}
}
Golang 代码
func maxArea(height []int) int {
result := 0
left := 0
right := len(height) - 1
for left < right {
curArea := 0
if height[left] < height[right] {
curArea = height[left] * (right - left)
left++
} else {
curArea = height[right] * (right - left)
right--
}
if curArea > result {
result = curArea
}
}
return result
}
C++ 代码
class Solution {
public:
int maxArea(vector<int>& height) {
int result = 0;
int left = 0;
int right = height.size() - 1;
while (left < right) {
int curHeight = min(height[left], height[right]);
int curWidth = right - left;
int curArea = curHeight * curWidth;
result = max(result, curArea);
if (height[left] < height[right]) {
left += 1;
} else {
right -= 1;
}
}
return result;
}
};
