いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode hard 84 Largest Rectangle in Histogram

投稿日:

こんにちは

今回の学びは

・スタックに託す。この高さは初めてなので、託す。低くなったら精算

 

問題はlargest-rectangle-in-histogram

(時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装  20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。

終始、わからないことは声にだして、明確にしていきましょう。

1,まずは入出力をしっかりおさえましょう。(問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと)

 

2,いくつかのソリューションを声にだして出してみましょう。(もちろんtime complexit, space complexityの分析や理由を付け加えて)

 

3,どれでいくか、一緒に決定しましょう。(理由付きでね、よろしく)

timespace analysis (時間とスペースの分析)は 〇〇です

 

場合によっては、pseudocode(擬似コード)をかいてみてもよい。

4、実装しましょう。

 

5、エッジケースとサンプルテストを忘れずに!

 

 

 

振り返り

「次のこの問題を解くばあい知っていればよい一つの事実とは?」

スタックに託す

この高さは初めてなので、託す。低くなったら精算

 

でこの問題が解けると、maximal rectangle問題が解けます。

 

まとめ

・スタックに託す。この高さは初めてなので、託す。低くなったら精算

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.