力扣00011.盛最多水的容器

发表于 分类于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 6 分钟
盛最多水的容器、贪心、数组、双指针、中等

题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：

你不能倾斜容器。

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

提示：

  • $n == height.length$
  • $2 <= n <= 10^5$
  • $0 <= height[i] <= 10^4$

解决方法

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxArea(std::vector<int>& height) {
        int max_area = 0;
        int left = 0;
        int right = height.size() - 1;
        while (left < right) {
            int current_area = std::min(height[left], height[right]) * (right - left);
            max_area = std::max(max_area, current_area);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return max_area;
    }
};

结果

执行用时 : 72 ms, 击败 73.27% 使用 C++ 的用户

内存消耗 : 58.09 MB, 击败 17.81% 使用 C++ 的用户

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int maxArea(int[] height) {
        int maxArea = 0;
        int left = 0;
        int right = height.length - 1;
        while (left < right) {
            int currentArea = Math.min(height[left], height[right]) * (right - left);
            maxArea = Math.max(maxArea, currentArea);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
}

结果

执行用时 : 4 ms, 击败 60.64% 使用 Java 的用户

内存消耗 : 56.42 MB, 击败 5.85% 使用 Java 的用户

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def maxArea(self, height):
        max_area = 0
        left = 0
        right = len(height) - 1
        while left < right:
            current_area = min(height[left], height[right]) * (right - left)
            max_area = max(max_area, current_area)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max_area

结果

执行用时 : 148 ms, 击败 13.12% 使用 Python 的用户

内存消耗 : 21.30 MB, 击败 5.26% 使用 Python 的用户

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_area = 0
        left = 0
        right = len(height) - 1
        while left < right:
            current_area = min(height[left], height[right]) * (right - left)
            max_area = max(max_area, current_area)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max_area

结果

执行用时 : 156 ms, 击败 72.12% 使用 Python3 的用户

内存消耗 : 27.78 MB, 击败 5.13% 使用 Python3 的用户

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maxArea(int* height, int heightSize) {
    int max_area = 0;
    int left = 0;
    int right = heightSize - 1;
    while (left < right) {
        int current_area = (height[left] < height[right]) ? height[left] * (right - left) : height[right] * (right - left);
        max_area = (current_area > max_area) ? current_area : max_area;
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return max_area;
}

结果

执行用时 : 76 ms, 击败 42.07% 使用 C 的用户

内存消耗 : 12.04 MB, 击败 80.31% 使用 C 的用户

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int MaxArea(int[] height) {
        int maxArea = 0;
        int left = 0;
        int right = height.Length - 1;
        while (left < right) {
            int currentArea = Math.Min(height[left], height[right]) * (right - left);
            maxArea = Math.Max(maxArea, currentArea);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }
}

结果

执行用时 : 292 ms, 击败 5.03% 使用 C# 的用户

内存消耗 : 60.38 MB, 击败 6.09% 使用 C# 的用户

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let maxArea = 0;
    let left = 0;
    let right = height.length - 1;
    while (left < right) {
        const currentArea = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, currentArea);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
};

结果

执行用时 : 68 ms, 击败 86.66% 使用 JavaScript 的用户

内存消耗 : 55.49 MB, 击败 5.07% 使用 JavaScript 的用户

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function maxArea(height: number[]): number {
    let maxArea: number = 0;
    let left: number = 0;
    let right: number = height.length - 1;
    while (left < right) {
        const currentArea: number = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, currentArea);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}

结果

执行用时 : 76 ms, 击败 71.65% 使用 TypeScript 的用户

内存消耗 : 57.73 MB, 击败 5.08% 使用 TypeScript 的用户

PHP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {

    /**
     * @param Integer[] $height
     * @return Integer
     */
    function maxArea($height) {
        $maxArea = 0;
        $left = 0;
        $right = count($height) - 1;
        while ($left < $right) {
            $currentArea = min($height[$left], $height[$right]) * ($right - $left);
            $maxArea = max($maxArea, $currentArea);
            if ($height[$left] < $height[$right]) {
                $left++;
            } else {
                $right--;
            }
        }
        return $maxArea;
    }
}

结果

执行用时 : 180 ms, 击败 80.25% 使用 PHP 的用户

内存消耗 : 25.96 MB, 击败 96.30% 使用 PHP 的用户

Swift

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    func maxArea(_ height: [Int]) -> Int {
        var maxArea = 0
        var left = 0
        var right = height.count - 1
        while left < right {
            let currentArea = min(height[left], height[right]) * (right - left)
            maxArea = max(maxArea, currentArea)
            if height[left] < height[right] {
                left += 1
            } else {
                right -= 1
            }
        }
        return maxArea
    }
}

结果

执行用时 : 628 ms, 击败 5.38% 使用 Swift 的用户

内存消耗 : 19.45 MB, 击败 5.38% 使用 Swift 的用户

Kotlin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    fun maxArea(height: IntArray): Int {
        var maxArea = 0
        var left = 0
        var right = height.size - 1
        while (left < right) {
            val currentArea = minOf(height[left], height[right]) * (right - left)
            maxArea = maxOf(maxArea, currentArea)
            if (height[left] < height[right]) {
                left++
            } else {
                right--
            }
        }
        return maxArea
    }
}

结果

执行用时 : 400 ms, 击败 45.71% 使用 Kotlin 的用户

内存消耗 : 51.34 MB, 击败 68.57% 使用 Kotlin 的用户

Dart

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
  int maxArea(List<int> height) {
    int maxArea = 0;
    int left = 0;
    int right = height.length - 1;
    while (left < right) {
      int currentArea = height[left] < height[right]
          ? height[left] * (right - left)
          : height[right] * (right - left);
      maxArea = currentArea > maxArea ? currentArea : maxArea;
      if (height[left] < height[right]) {
        left++;
      } else {
        right--;
      }
    }
    return maxArea;
  }
}

结果

执行用时 : 332 ms, 击败 22.22% 使用 Dart 的用户

内存消耗 : 167.73 MB, 击败 100.00% 使用 Dart 的用户

Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func maxArea(height []int) int {
    maxArea := 0
    left := 0
    right := len(height) - 1
    for left < right {
        currentArea := min(height[left], height[right]) * (right - left)
        if currentArea > maxArea {
            maxArea = currentArea
        }
        if height[left] < height[right] {
            left++
        } else {
            right--
        }
    }
    return maxArea
}

结果

执行用时 : 76 ms, 击败 20.43% 使用 Go 的用户

内存消耗 : 8.11 MB, 击败 48.25% 使用 Go 的用户

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# @param {Integer[]} height
# @return {Integer}
def max_area(height)
  max_area = 0
  left = 0
  right = height.length - 1
  while left < right
    current_area = [height[left], height[right]].min * (right - left)
    max_area = [max_area, current_area].max
    if height[left] < height[right]
      left += 1
    else
      right -= 1
    end
  end
  max_area
end

结果

执行用时 : 128 ms, 击败 85.71% 使用 Ruby 的用户

内存消耗 : 213.06 MB, 击败 14.29% 使用 Ruby 的用户

Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
object Solution {
  def maxArea(height: Array[Int]): Int = {
    var maxArea = 0
    var left = 0
    var right = height.length - 1
    while (left < right) {
      val currentArea = math.min(height(left), height(right)) * (right - left)
      maxArea = math.max(maxArea, currentArea)
      if (height(left) < height(right)) {
        left += 1
      } else {
        right -= 1
      }
    }
    maxArea
  }
}

结果

执行用时 : 706 ms, 击败 28.57% 使用 Scala 的用户

内存消耗 : 75.38 MB, 击败 76.19% 使用 Scala 的用户

Rust

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
impl Solution {
    pub fn max_area(height: Vec<i32>) -> i32 {
        let mut max_area = 0;
        let mut left = 0;
        let mut right = height.len() - 1;
        while left < right {
            let current_area = std::cmp::min(height[left], height[right]) * (right - left) as i32;
            max_area = std::cmp::max(max_area, current_area);
            if height[left] < height[right] {
                left += 1;
            } else {
                right -= 1;
            }
        }
        max_area
    }
}

结果

执行用时 : 4 ms, 击败 98.87% 使用 Rust 的用户

内存消耗 : 3.07 MB, 击败 6.02% 使用 Rust 的用户

Racket

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Racket 的用户

内存消耗 : MB, 击败 % 使用 Racket 的用户

Erlang

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Erlang 的用户

内存消耗 : MB, 击败 % 使用 Erlang 的用户

Elixir

暂时未解决

1

结果

执行用时 : ms, 击败 % 使用 Elixir 的用户

内存消耗 : MB, 击败 % 使用 Elixir 的用户