Leet Codeで「一番多くの水を入れるコンテナ」問題を解く

11. 一番多くの水を入れるコンテナ

タイプ: ミディアム
好きな人: 26.5K
嫌いな人: 1.4K

この質問をした会社
会社 : 質問された回数

Microsoft 4
Google 4
Amazon 3
Adobe 2
Bloomberg 2
Apple 9
Facebook 4
Uber 3
Oracle 2
TikTok 2
Goldman Sachs 5
Intel 4
Swiggy 4
ByteDance 3
VMware 3
Qualtrics 3
Intuit 3
Flipkart 2
Zoho 2
Samsung 2
eBay 2
Walmart Labs 2
Yandex 2
Yahoo 2
Cisco 2
tcs 2
Tesla 2
C3 IoT 2
Arcesium 2
DE Shaw 2
JPMorgan 2
Wix 1

長さ n の整数配列 height が与えられています。i 番目の線は (i, 0) と (i, height[i]) の二つの端点を持つように n 本の垂直線が描かれています。
x軸と共にコンテナを作るための2本の線を見つけて、そのコンテナが最も多くの水を含むようにしてください。
コンテナが保持できる最大の水の量を返してください。
コンテナを傾けることはできないことに注意してください。

例 2:
入力: height = [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

直感:

このコードはヒストグラム内の2本の線の間の最大の領域を見つけることを目指しています。ここでの線はバーの高さを表しています。

アプローチ:

• ヒストグラムの両端にポインタを初期化します（LeftPointerを0、RightPointerを最後の要素に設定します）。
• LeftPointerがRightPointerより小さい間：
• LeftPointerとRightPointerの高さで形成される線の間の領域を計算します。
• 現在の領域がより大きい場合は、MaximumAreaを更新します。
• より短い線を指しているポインタを内側（他のポインタの方向）に動かします。
• ポインタが合うまでステップ2を繰り返します。

複雑さ:

時間複雑性: O(n) ここで、nはheight配列の要素数です。配列を一度通過します。
空間複雑性: O(1) 入力サイズに関わらず、一定量の追加スペースを使います。

コード:

class Solution {
    public int maxArea(int[] height) {
        int MaximumArea = 0;
        int LeftPointer = 0;
        int RightPointer = height.length - 1;

        while(LeftPointer < RightPointer){
            if(height[LeftPointer] < height[RightPointer]){
                MaximumArea = Math.max(MaximumArea , height[LeftPointer] *(RightPointer - LeftPointer));
                LeftPointer++;
            }
            else{
                MaximumArea = Math.max(MaximumArea ,height[RightPointer] *(RightPointer - LeftPointer));
                RightPointer--;
            }
        }

        return MaximumArea;
    }
}

フルスクリーンモードを終了

ハッピーコーディング、
shiva

こちらの記事はdev.toの良い記事を日本人向けに翻訳しています。
https://dev.to/leetcode/solving-the-container-with-most-water-problem-on-leet-code-51f5