課題の説明#
長さ n の整数配列 height が与えられます。n 本の垂直線があり、i 番目の線の 2 つの端点は (i, 0) と (i, height [i]) です。
x 軸と共に容器を構成する 2 本の線を見つけ、それらが最大の水を含む容器を作ることができます。
容器に貯蔵できる最大の水量を返します。
注意:容器を傾けることはできません。
例 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
アイデア#
- 配列を両端から中央に向かって走査し、容器の水の上限は低い方になります。走査ポインターの距離をこの値で乗算すると、水の容量が得られます。
- ポインターを移動するたびに、現在の水の容量と最大の水の容量(初期値は 0)を比較し、最大値を取得します。
- 各移動では、片方のポインターのみを移動させます。低い方のポインターを中央に向かって移動させます。なぜなら、低い方のポインターが水の容量に影響するからです。
解法#
/**
* @param {number[]} height
* @return {number}
*/
var maxArea = function (height) {
let l = 0, r = height.length - 1;
let ans = 0, max = 0;
while (l < r) {
let h = height[l] < height[r] ? height[l] : height[r];
max = (r - l) * h;
height[l] < height[r] ? l++ : r--;
ans = max > ans ? max : ans;
}
return ans;
};