盛最多水的容器

题目

给你 n 个非负整数 a₁, a₂, ..., aₙ, 每个数代表坐标中的一个点 (i, aᵢ). 在坐标内画 n 条垂直线, 垂直线 i 的两个端点分别为 (i, aᵢ) 和 (i, 0). 找出其中的两条线, 使得它们与 x 轴共同构成的容器可以容纳最多的水.

提示:

• n == height.length
• 2 <= n <= 10⁵
• 0 <= height[i] <= 10⁴

示例

输入: [1, 8, 6, 2, 5, 4, 8, 3, 7]

输出: 49

解释: 以第二个元素 8 和最后一个元素 7 围成的区域盛水量最大, 此时宽度为 7, 根据短板效应, 高度最大为 7, 面积即 49.

题解

JavaScript

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
  let i = 0,
    j = height.length - 1
  let max = 0

  while (i < j) {
    // 找出短板
    const min = Math.min(height[i], height[j])

    // 短板乘以宽度即面积
    max = Math.max(min * (j - i), max)

    // 以压缩宽度的代价来寻找最优短板
    if (height[i] < height[j]) {
      i++
    } else {
      j--
    }
  }

  return max
}

Rust

use std::cmp;

pub fn max_area(height: Vec<i32>) -> i32 {
    let (mut i, mut j, mut max) = (0, height.len() - 1, 0);

    while i < j {
        let min = cmp::min(height[i], height[j]);
        max = cmp::max(max, min * (j - i) as i32);

        if height[i] < height[j] {
            i += 1;
        } else {
            j -= 1;
        }
    }

    max
}