この記事は、主に、以下で詳述するように、Javaプログラミングアレイの最大のサブマトリックスに関連するコンテンツを研究しています。
良い人に会うことはあなたの人生を変えることができます。良い本に会うのですね。
最近、Zuo Chengyun氏の「プログラマーコードインタビューガイドのアルゴリズムとデータ構造の質問の最適なソリューション」を読んだとき、私は多くの洞察を得ました。この分野で趣味を持っているブロガーも見に行くことをお勧めします。
本で説明されているスタックベースのアレイの最大のマトリックスのアルゴリズムは非常に古典的ですが、ブロガーの能力は限られており、アルゴリズムの本質を完全に理解することができませんでした。ただし、このアイデアに基づいて、ブロガーはこのタイプの問題に対処するための簡単なアルゴリズムを思いつきました。これは次のように要約されています。
核となるアイデア
最初に写真を見てみましょう。私たちはそれを大まかに理解することができます。
図に示すように、各ラウンドは操作であり、私たちのコアは各ラウンドの内部操作です。
各レイヤーの最大長を連続的に途切れることなく計算します
言い換えれば、私たちは下からトップラウンドを計算するための最も重要な配列であり、各ラウンドでこのラウンドで取得できる連続最大サブマトリックスの領域を計算できます。次に、各ラウンドの最大のデータを比較し、アレイの最大の連続サブマトリックスの面積を見つけるために戻るだけです。
コード
さて、上記のコアのアイデアがレイアウトされていると、コードの作成を開始できます。 （私はそれをあまり明確に言ったとは思わないが、私を許してください）。
パッケージstack_and_queue;/*** @author guo pu <br>*配列に基づいて最大の連続長方形領域の領域を計算します*/public class maxRectangle {public static void main（string [] args）{integer [] arr = {2、1、3、5、7、6、6、4、4}; maxRectangleArea（arr）; system.out.println（ "配列内の最大の連続長方形領域の領域は：" + maxRectangle）;}/*** @Param arr* @return array*/private static integer maxrectearea（integer [] arn []（integer） （int i = 1; i <= arr.length; i ++）{//現在のラウンドで蓄積された連続長の一時的な値が実装されているint temple = 0; //このラウンドの高さで最大連続長を記録するint templen_max = 0; （int j = 1; j <= arr.length; j ++）{if（arr [j -1]> = i）{templen += 1; templen_max = templen;} else {templen = 0;}} result [i -1] = i * templen_max;レイヤーの： "+templen_max）;} //結果セット配列の最大数値値の数値を見つけます。つまり、int maxarea = 0が見つかった連続領域の最大長方形のドメインの領域を見つけます。 Maxareaを返すことによって得られる最大連続長方形フィールドの面積;}}コードのコメントも比較的包括的であるため、詳細はあまり説明しません。
テスト
以下は、配列のテストです。まず、この記事の冒頭にある写真に示されている配列でテストしましょう。
integer [] arr = {2,1,3,5,7,6,4} ・・・・配列内の最大の連続長方形の面積は次のとおりです。
次に、配列内の要素の値を変更して、結果が正しいかどうかを確認するためにさらにテストします。
integer [] arr = {2,1,3,1,7,6,4} ・・・・アレイ内の最大の連続長方形領域の面積は次のとおりです。
ブロガー自身がそれをテストした後、アルゴリズムは正常に機能します。 :)
最適化パーツ
最適化の部分といえば、最初に見ることができるのは、最後のステップで結果セット配列の最大値を見つけることです。
実際、実際に別の変数を適用して、これまでにラウンドの最大のサブマトリックスの領域を記録できます。ただし、この最適化は大きな役割を果たしておらず、時間の複雑さに大きな改善はありません。
もう1つのポイントは、より良いエントリポイントは、各ラウンドの計算を実行するときに判断を追加して、現在のラウンドの前に下方にサイクリングするかどうかを決定することだと思います。配列内の要素が大きく変動する場合、最適化レベルは依然として非常に良好です。
要約します
この小さなアルゴリズムはより絶妙であり、より欠陥のある唯一のことは、時間の複雑さがわずかに激しくなることです。読者が比較的低い時間の複雑さを持つアルゴリズムを探している場合は、迂回してください。
結果を見つけたいだけなら、それはかなり良いことです。少なくとも、それは暴力的なコンピューティング方法よりもはるかに効率的です。
上記は、Javaプログラミングアレイの最大サブマトリックスに対する単純なソリューションに関するこの記事のすべての内容です。私はそれが誰にでも役立つことを願っています。興味のある友人は、このサイトの他の関連トピックを引き続き参照できます。欠点がある場合は、それを指摘するためにメッセージを残してください。このサイトへのご支援をありがとうございました！