[leetcode]問題解答と解説。11. Container With Most Water [JavaScript]
皆さんleetCode好きですよね。私も好きです。
なかなかやる機会がないのですよね。
leetCodeの使い方や解説ではなく実際に問題を解決するために何をしたか
をメモ書きして行きます
私はある決意をして今挑んでいます。
モチベーションを保つためだけにこれをやっています。
では今日のleetCode。
【11. Container With Most Water】の解決策と方法。自分がまず挑戦して
やったことをさらけ出します。
※下にある自分のコードは自分で設けた制限時間内に書けたところまです。
これは
「私は年末までこれを続けたらどんなleetCoderになるか」のシリーズ。
実験的ブログ更新です。
森田賢二のleetCode
[leetcode] 11. Container With Most Water ルール
長さnの整数配列heightが与えられており、i番目の直線の2つの端点が(i, 0)と(i, height[i])となるように、n本の垂直線が引かれている。
x軸と一緒になって容器を形成し、その容器が最も多くの水を含むような2本の直線を求めよ。
容器が貯めることのできる水の最大量を返せ。
なお、容器を斜めにすることはできません。
exampleは実際の問題ページを見てください
[leetcode] 11. Container With Most Water 問題ページ
[leetcode] 11. Container With Most Water
my code is not completed
var maxArea = function(height) {
let mid = Math.floor(height.length / 2)
let right = mid + 1
let left = mid
while(right < height.length || left >= 0){
right++
left--
}
};時間切れ。
やりたかったことは、最初真ん中にtow pointerを集めて、それぞれ左と右にずれていって、右が大きくなったら、計算、Math.maxを使って最大を一次補完、次は反対方向にひとつづつずれていく。それを繰り返して、左右がどっちも端に到達した時に一時保存していたものがmaxになるというイメージでした
[leetcode] 11. Container With Most Water。discussの中の一つの解答例
数ある中からJavaScriptのもので、理解しやすい解説をピックアップしました。
discussから見ればさらにもっと違う方法で真似したくなるものがあるかもしれない
JavaScriptでfilterされている、discussはこちらから
function maxArea(height: number[]): number {
let area = -Infinity // ネガティブな無限数を初期値にする
let start = 0
let end = height.length - 1
while (start < end) {
const l = height[start]
const r = height[end]
area = Math.max(area, (end - start) * Math.min(l, r)) // 最大の横幅x低い方。低い方が最大で入る水の高さだから。(end-start)は幅
l > r ? end-- : start++ // 左の方が大きかったら右を次に
}
return area
}- 両サイドから
- あとは似てそう
