跳至主要內容

11. Container With Most Water

11. Container With Most Wateropen in new window

🟠   🔖  贪心 数组 双指针  🔗 LeetCodeopen in new window

题目

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]

Output: 49

Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]

Output: 1

Constraints:

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

题目大意

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

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

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

说明：你不能倾斜容器。

解题思路

这一题可以用对撞指针的思路，首尾分别 2 个指针，每次移动以后都分别判断长宽的乘积是否最大。

从示例中可以看出，如果确定好左右两端的直线，容纳的水量是由 左右两端直线中较低直线的高度 * 两端直线之间的距离 所决定的。所以我们应该使得 较低直线的高度尽可能的高，这样才能使盛水面积尽可能的大。

可以使用对撞指针求解，移动较低直线所在的指针位置，从而得到不同的高度和面积，最终获取其中最大的面积。具体做法如下：

  1. 使用两个指针 left，right。left 指向数组开始位置，right 指向数组结束位置。
  2. 计算 left 和 right 所构成的面积值，同时维护更新最大面积值。
  3. 判断 left 和 right 的高度值大小。
    1. 如果 left 指向的直线高度比较低，则将 left 指针右移。
    2. 如果 right 指向的直线高度比较低，则将 right 指针左移。
  4. 如果遇到 left == right，跳出循环，最后返回最大的面积。

代码

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  let left = 0;
  let right = height.length - 1;
  let _height, width;
  let max = 0;
  while (left < right) {
    width = right - left;
    if (height[left] > height[right]) {
      _height = height[right];
      right--;
    } else {
      _height = height[left];
      left++;
    }
    max = Math.max(max, _height * width);
  }
  return max;
};

相关题目

相关题目
- [42. 接雨水](https://leetcode.com/problems/trapping-rain-water)
- [2517. 礼盒的最大甜蜜度](https://leetcode.com/problems/maximum-tastiness-of-candy-basket)
- [2560. 打家劫舍 IV](https://leetcode.com/problems/house-robber-iv)
Copyright © 2024 2xiao