[Leetcode]Container With Most Water

2171 ワード
アルゴリズム#アルゴリズム# テキストリンク

問題)パラメータheightは数値からなる配列である.グラフィックで表すと、y軸の値であり、高さの値があります.
[1,8,6,2,5,4,8,3,7]を下図に示します.
そのグラフに水があるとき、水を入れることができる最大面積の値を返してください.

私の考えの論理

  • の最大幅値(戻る値)を変数maxに設定します.
  • の2つの欄のインデックス値をlt,rtに設定します.(lt = left, rt = right)
  • 二層砲口内に高さと幅を設定します.(いずれの場合も幅値を求め、最大値と照合する必要があります)
    heightはheight[lt]およびheight[rt]においてより小さな値として計算される.
    widthはrtからltを減算した値です.
  • hおよびwに乗じた値をmaxと比較した後、maxより大きい場合、maxに対応する値を割り当てる.
    • 最終的に得られた最大値
  • を返します.
    • コードは以下の通りです.
    function getMaxArea(height) {
let max = 0;
  
  for(let lt = 0; lt <height.length-1; lt++){
    for(let rt = lt +1; rt<height.length; rt++){
  let h = Math.min(height[lt], height[rt]);
  let w = rt - lt;

      if(max <h*w) max = h*w;    
    }
  }
  return max 
  
}
    二重砲口以外に、他の方法はありますか?
    function getMaxArea(height) {
 let lt = 0;
   let rt = height.length -1;
   let max = 0

  while(lt < rt){
    let h = Math.min(height[lt], height[rt]);

    let w = rt - lt;

    if(max < h*w) max = h*w;
   else lt++
   
  } 
  while(lt < rt){
    let h = Math.min(height[lt], height[rt]);

    let w = rt - lt;

    if(max < h*w) max = h*w;
   else rt--
   
  } 
   }
   return max}
  • の先頭のインデックスをlt、右端(終了)のインデックスをrtに設定します.
  • lt比rtが左側にある場合は、ドアを回します.hとwを求める方式は上記と同様であり、幅がmaxより大きい場合はmaxに対応する幅値を指定する.
  • そうでなければltを右に1格移動し,照合して最終的な最大値を求める.
  • rtの場合、1つのグリッドを左に移動し、値を合わせた後、最終的な最大値を返します.
    • 以上のように正解が得られたが,考えてみればltとrtが中間にある場合の数を考慮していないため,一定の限界がある.
    なんといっても二重砲口で開く方式で正解率100%は、二重砲口です^^

    追加)


    上のwhileの2つのソリューションを用いて,小解の欠点を補った.
    出典:YONGHYUNのブログでは、とても良い方法なので見逃せません(?)
     function(height) {
    let result = 0;
    let i = 0;
    let j = height.length-1 // #1
    while(i < j){ // #2
        result = Math.max(result, Math.min(height[i], height[j])*(j-i)) // #3
        height[i] < height[j] ? i++ : j-- // #4
    } 
    return result // #5
};

    🍯 の最後の部分


    実は...ほとんど书き终わってなくなって、第2回书きます^^ははは、みんなが早めに保存することができることを望んで、ははははは
    positionプロパティ/23号/03-6(3)
    LeetCode#2 Add Two Numbers