こんにちは
今回の学びは
・公式と捜査を意識する
・細かい意見が拝見できるhttps://leetcode.com/articles/
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は
普通にやると
tO(N^2)ですべての組み合わせでmaxを取っていけばクリアです。
量子コンピューティングがあればこれで通ります。
ないので、
よりよいアルゴリズムを考える。これが楽しいパートです。
お仕事ではありません。これが楽しいパートです。（自己暗示）
楽しいと感じないと他の猛者たちに食われてしまう
とか理由ではなく、純粋に問題を効率よく解決する方法を考えるのは楽しいパートです。（しつこい）
ということで
配列の中から、連続するカラム1,2を探すのでダブルポインター戦略を考えたいと思います。
さらに、ポインターをどっからスタートしたらいいかという問いには
最大のポイントからつまりは両脇からスタートして徐々に内側にづらしていけばよいと思います。
そうすればからナズ、最大のポイントを通るので。
さらにバーが小さい方を一個ずらすというアイデアを浮かび、これは正しいです。
非常に悩んだのは、
もしバーの高さが全く同じ出会った場合、左か右のどちらのポインターをずらせばいいのか？という疑問です。
なぜなら、右と左のどちらを選ぶかによって
そのあとの軌跡が変わるからです。
適当な例を挙げてみれば、わかることです。
高さが同じ場合は、左をずらすパターンと右をずらすパターンの両方を感がないといえないのかk！？そんな風に思ってしまいます。
するといきなりアルゴリズムがtO(^N)と肥大化してしまいます。
といことで
ヒューリスッティック的には良さそうなんだけど、それを言語化して安心したいところです。
そんな中、納得がいった説明がleetcodeの記事articles/container-with-most-waterにありました。
salek 6 October 5, 2018 4:06 AMReport
@kingaslan30 No, the algo is correct. The only scenario where you can increase the area after this point is if there are two taller lines between the two of the same height, in which case 'l' and 'r' will reach them regardless of the order you move them at this point.
とうものです。どちらを選んでも良い。その理由は、同じバー（便宜上、高さ６、幅5としましょう。）にポインターがある地点でのAreaを超えるエリアを内側でなし得るのは、両方のバーが現在のバーの高さが高い地点でないと有り得ません。仮に内側に高さ8というバーがあったとしても幅が4に減少し、片方はバー高さ６ででしばられているので 6 * 4で、同じバーの時点の6*5には至りません。両方のバーの高さが高くなって初めて高さ30と高さ25とかに出くわすと幅が2とかであれば、min(30, 25)*2ということで50でArea更新ということにないす。つまりは同じバーの場合でも内側にいけば、その高さのバーにポインターがいる限りMaAreaは更新さり得ないとうことです。
大事なことはどうやったこの
法則に素早く気づくことができたのか？再現可能にするにはどのような思考軌跡を
たどればいいのか、だと思いますので。
ツラツラ復習していきたいと思います。
問題は配列があります、二つの点を捜査したとき
与えられた時に、距離 * min(高さ1, 高さ2)がmaxになるのは、どこか？
というもので、
ポインターは距離を縮めていく。
つまりは高さが高くならない限り、面積は増えない！
高さは、両方の高さが高くなって初めて、増える！
という、
かんがえかたですね。なので
再現性があるかは、微妙ですが、
公式を立てて捜査の流れと照らしあわせる！というものです。
今回でいえば
MaxArea = 距離 * min(高さ1, 高さ2)
捜査は挟み撃ち（徐々に距離が小さくなる）
という
条件ですんね。
・公式と捜査を意識する
いい学びだと思います。
ふう〜
pseudocode（擬似コード）をかいてみますか。
。。。
実際の実装はこちら
。。。
実装後です。timespace analysis (時間とスペースの分析）は ◯◯
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
これはわかってしまえば実装はめちゃめちゃ簡単。ダブルポインターで、低かったらずらす。
まとめ
・公式と捜査を意識する
以上です