直方圖中最大的矩形

問題概述

任務是找出直方圖中可以形成的最大矩形區域。直方圖中每個長條的寬度為 1，每個長條的高度由非負整數陣列給出。

例如，給定高度陣列 [2, 1, 5, 6, 2, 3]，直方圖中最大的矩形面積為 10。

解決方法

使用基於堆疊的方法可以有效地解決該問題。這種方法涉及維護一個堆疊來追蹤直方圖條形的索引，使我們能夠在線性時間內計算最大矩形面積。以下是此演算法的詳細分解：

1. 初始化變數

• len：高度數組的長度。
• stack：用於儲存直方圖條形索引的空堆疊。
• max：一個變量，用於追蹤迄今為止找到的最大矩形區域。
• h：從堆疊中彈出的欄位的高度。
• w: 高度為h形成的矩形的寬度。

2. 迭代 Heights 陣列

我們從左到右迭代 heights 數組，並在數組末尾添加一個高度為 0 的最終虛擬條，以確保所有條都被處理。

迭代步驟：

• 壓入目前柱的索引：對於每個柱，將其索引壓入堆疊。然而，在此之前，我們需要確保目前的柱比儲存在堆疊頂部的索引處的柱高。如果不是，我們從堆疊中彈出條，以使用彈出索引處的條作為最小條（即矩形的高度）來計算可以形成的矩形面積。

• 從堆疊中彈出並計算面積：

  • 從堆疊中彈出頂部索引。此索引表示矩形中最小條形的高度。
  • 計算矩形的寬度。如果彈出後堆疊為空，則表示彈出的條是迄今為止最小的，並且其寬度從數組的開頭延伸到當前索引。否則，寬度由當前索引與現在位於堆疊頂部的索引之間的距離減一確定。
  • 使用高度和寬度計算矩形的面積，如果該面積較大，則更新 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 是直方圖中的條形數量。每個條最多從堆疊中壓入和彈出一次。
• 空間複雜度： 用於追蹤索引的堆疊的 O(n)。

以上是直方圖中最大的矩形的詳細內容。更多資訊請關注PHP中文網其他相關文章！