ヒストグラムの最大の長方形

問題の概要

タスクは、ヒストグラム内で形成できる最大の長方形領域を見つけることです。ヒストグラムの各バーの幅は 1 で、各バーの高さは非負の整数の配列で与えられます。

たとえば、高さ配列 [2, 1, 5, 6, 2, 3] の場合、ヒストグラム内の最大の四角形領域は 10 です。

解決策のアプローチ

この問題は、スタックベースのアプローチを使用して効率的に解決できます。このアプローチには、ヒストグラム バーのインデックスを追跡するスタックを維持することが含まれており、線形時間で最大の四角形領域を計算できるようになります。アルゴリズムの詳細な内訳は次のとおりです:

1. 変数の初期化

• len: 高さの配列の長さ。
• stack: ヒストグラム バーのインデックスを保存するために使用される空のスタック。
• max: これまでに見つかった最大の四角形領域を追跡する変数。
• h: スタックからポップされるバーの高さ。
• w: 高さ h で形成される長方形の幅。

2. 高さの配列を反復処理します

高さの配列を左から右に繰り返し処理し、高さ 0 の最終的な仮想バーを配列の最後に追加して、すべてのバーが処理されるようにします。

反復のステップ:

• 現在のバーのインデックスをプッシュ: 各バーに対して、そのインデックスをスタックにプッシュします。ただし、その前に、現在のバーがスタックの最上部に格納されているインデックスのバーよりも高いことを確認する必要があります。そうでない場合は、スタックからバーをポップし、ポップされたインデックスのバーを最小のバー (つまり、長方形の高さ) として使用して形成できる長方形の面積を計算します。

• スタックからポップして面積を計算:

  • スタックから最上位のインデックスをポップします。このインデックスは、長方形内の最小のバーの高さを表します。
  • 長方形の幅を計算します。ポップ後にスタックが空の場合は、ポップされたバーがこれまでで最も小さく、その幅が配列の先頭から現在のインデックスまでであることを意味します。それ以外の場合、幅は現在のインデックスとスタックの最上位にあるインデックスとの間の距離から 1 を引いたものによって決まります。
  • 高さと幅を使用して長方形の面積を計算し、この面積が大きい場合は max 変数を更新します。

3. スタック内の残りのバーを処理します

すべてのバーを反復処理した後、スタックにまだいくつかのバーが残っている可能性があります。右側には短いバーがなかったため、これらのバーの高さは処理されません。これらの残りのバーも同様に、スタックからポップして面積を計算することで処理する必要があります。

コードの詳しい説明

各部分を説明するコメントを含む JavaScript コードを次に示します。

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
  var len = heights.length;
  var stack = [];
  var max = 0;
  var h = 0;
  var w = 0;

  // Iterate through the heights array
  for (var i = 0; i <= len; i++) {
    // Ensure the loop processes the virtual bar with height 0 at the end
    while (stack.length && (i === len || heights[i] <= heights[stack[stack.length - 1]])) {
      // Pop the top index from the stack
      h = heights[stack.pop()];
      // Calculate the width of the rectangle
      w = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      // Update the maximum area found so far
      max = Math.max(max, h * w);
    }
    // Push the current index onto the stack
    stack.push(i);
  }

  return max;
};

複雑さの分析

• 時間計算量: O(n)、n はヒストグラム内のバーの数です。各バーはスタックから最大 1 回プッシュおよびポップされます。
• 空間の複雑さ: インデックスを追跡するために使用されるスタックの O(n)。

以上がヒストグラムの最大の長方形の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。