演算法面試：如何求直方圖中的最大矩形？

題目與適用場景

給定陣列 heights，每個數表示一根寬度為 1 的柱子。合法矩形需要覆蓋一根或多根連續柱子， 底邊落在基線上，高度不能超過覆蓋區間內最矮的柱子。回傳最大的矩形面積。

heights = [2, 1, 5, 6, 2, 3]
answer = 10

最優矩形覆蓋索引 2..3：高度為 5，寬度為 2，面積為 10。標準約束是 1 <= heights.length <= 100000、0 <= heights[i] <= 10000。本文額外約定空陣列回傳 0。 在標準約束下，面積最多為 10^9，JavaScript 的 number 可以精確表示。

目前英文面試準備資料與一份獨立的中文公開題解都把這道原題作為單調堆疊練習；原始題面和目前 DSA 指南也採用相同的單位寬度模型與約束。因此可將其視為有代表性的 coding 題，無須歸屬 某家公司，也不聲稱無法核驗的出現頻率。

面試官在考察什麼

第一，看你能否在不列舉所有左右邊界的前提下涵蓋全部候選矩形。選定一個高度後，它的最寬矩形 會一直延伸到左右第一個嚴格更矮的柱子。幾何問題因此轉化為「尋找最近更小元素」。

第二，看你能否從這個關係推導資料結構。遞增堆疊保留右邊界尚未確定的柱子。更矮柱出現時，會 一次關閉一根或多根柱子的候選矩形：目前索引是它們右側第一個更矮位置，堆疊中保存的起點已經 編碼了它們能向左延伸到哪裡。

第三，看你是否能正確處理相等高度與陣列邊界。相等高度不應留下起點不同、互相競爭的堆疊項； 掃描結束時還在堆疊裡的柱子也必須取得右邊界。可靠實作會明確這兩個規則，而非只背寬度公式。

最後，巢狀的 while 需要攤銷分析。一次迴圈可能彈出多個堆疊項，但每個堆疊項只會被推入一次、 彈出一次，所有堆疊操作的總數仍是線性的。

回答前要釐清的問題

• 每根柱子的寬度都是 1 嗎？ 是。寬度可變時，左邊界狀態和面積公式都要調整。
• 矩形必須覆蓋連續柱子嗎？ 是。中間的矮柱不能被跳過。
• 高度可以為零或重複嗎？ 可以。零會隔斷正面積矩形；相等高度需要一致的推入規則。
• 陣列可能為空嗎？ 標準題面排除了空陣列，本文實作會回傳 0 作為明確擴充。
• 只回傳面積嗎？ 是。若要回傳座標，還要保留獲勝矩形的起點、終點、高度並定義並列規則。
• 可以修改輸入嗎？ 不需要；本文使用虛擬哨兵，不會向原陣列附加元素。
• 面積會溢位嗎？ 給定約束下不會。正式介面若擴大範圍，應先計算上界，再按需要使用 bigint 或更寬整數。
• 必須達到線性時間嗎？ 是。O(n^2) 基線適合推導和測試，但無法滿足目標規模。

30 秒回答框架

「對高度為 h 的柱子，它的最寬合法矩形會在左右第一個更矮柱之前停止。我從左到右掃描，用 嚴格遞增高度的 (start, height) 堆疊。目前高度低於堆疊頂端時，目前索引就是頂端右側第一個 更矮邊界，於是彈出頂端並計算 height * (right - start)。我把彈出的 start 向左傳遞，因為 目前更矮柱能跨過剛移除的所有高柱。高度相等時保留更早的堆疊項。最後掃描一根虛擬的零高柱， 關閉剩餘矩形。每個堆疊項最多被推入、彈出一次，因此時間為 O(n)，輔助空間為 O(n)。」

逐步深入解法

步驟一：建立正確基線。

對每個區間 [left, right]，維護其中的最小高度。覆蓋整個區間的最大矩形面積是：

min(heights[left..right]) * (right - left + 1)

固定 left 後向右擴展並更新最小值，可得到 O(n^2) 時間、O(1) 空間的基準演算法。它無法 處理 n = 100000 的最壞輸入，卻很適合在小規模隨機陣列上驗證最佳化解法。

步驟二：反轉列舉方式。

不再為每個區間尋找最矮柱，而是選定一根柱子作為矩形的限制高度。若左右最近的嚴格更矮位置是 leftShorter 和 rightShorter，該柱可覆蓋：

(leftShorter + 1) .. (rightShorter - 1)
width = rightShorter - leftShorter - 1

這是以該柱高為限制時的最寬矩形。對所有限制高度取最大值，就是全域答案。

步驟三：讓遞增堆疊保存尚未關閉的柱子。

堆疊中保存 { start, height }，高度嚴格遞增。start 是在此前所有已關閉高柱被移除後，該 高度仍然有效的最早索引。新高柱從自身索引開始；新矮柱會關閉更高堆疊項，並繼承最早的彈出 起點。

以 [2, 1, 5, 6, 2, 3] 為例，索引 4 的高度 2 先彈出 6，得到 6 * 1；再彈出 5，得到 5 * 2 = 10。它繼承起點 2，因為高度 2 可以跨過剛才兩根高柱。堆疊中的高度 1 更矮，阻止它繼續向左延伸。

步驟四：定義相等高度和收尾規則。

目前高度與堆疊頂端相等時，保留較早堆疊項。兩者高度相同，但早期堆疊項起點更靠左，能得到的 最優矩形不會更窄。在索引 n 處掃描一根虛擬的高度 0 柱，可關閉所有正高度堆疊項，無須 修改輸入，也無須重複一套清空堆疊的面積邏輯。

步驟五：實作不變量並證明彈出計算。

interface StackBar {
  start: number
  height: number
}

export function largestRectangleArea(heights: number[]): number {
  const stack: StackBar[] = []
  let maxArea = 0

  for (let right = 0; right <= heights.length; right += 1) {
    const height = right === heights.length ? 0 : heights[right]
    let start = right

    while (stack.length > 0 && stack[stack.length - 1].height > height) {
      const bar = stack.pop()!
      maxArea = Math.max(maxArea, bar.height * (right - bar.start))
      start = bar.start
    }

    const top = stack[stack.length - 1]
    if (height > 0 && (!top || top.height < height)) {
      stack.push({ start, height })
    }
  }

  return maxArea
}

每輪掃描前保持三個不變量：

1. 堆疊內高度嚴格遞增。
2. 對每個堆疊項，從 start 到 right - 1 的所有已處理柱高都不低於它。
3. 這段範圍內不存在已處理的嚴格更矮柱；否則該堆疊項早已被彈出。

更矮高度出現時，不變量 2 和 3 說明被彈堆疊項可以延伸到 right - 1；目前柱又證明它不能 覆蓋 right。因此它的最大寬度恰好是 right - start，此時計算的面積已經完整。把彈出起點 交給目前高度是安全的，因為目前高度低於所有剛移除的柱子。跳過相等高度也是安全的，因為被保留 的同高堆疊項起點不會更晚。哨兵會關閉所有右側沒有真實矮柱的堆疊項。於是每一種可能的限制高度 都計算了自己的最大矩形，maxArea 就是全域最優值。

步驟六：驗證邊界輸入與複雜度。

固定案例應分別攻擊不同不變量：

更強的可執行驗證是：在大量小隨機陣列上，把單調堆疊結果與平方級基準演算法逐一比較。本文實作 已經通過 7 個固定案例，以及 20000 個長度為 0..8、高度為 0..7 的隨機陣列。可執行驗證 不能取代證明；上面的不變量負責涵蓋所有可能輸入。

每個正高度最多被推入一次、彈出一次，所以總時間為 O(n)。嚴格遞增輸入會讓全部 n 個堆疊項 保留到哨兵處，因此最壞輔助空間為 O(n)。

高品質示範回答

「我會先建立平方級基準：固定每個左邊界，向右擴展並維護最小高度。它涵蓋了所有區間，但無法 處理 10 萬根柱子的目標規模。重複出現的問題是：選定一個高度後，它在遇到更矮柱之前能延伸 多遠。這正是最近更小邊界，可以用單調堆疊解決。

我的堆疊保存每個尚未關閉高度的最早有效起點，並保持高度嚴格遞增。掃描到索引 right 時， 只要堆疊頂端高於目前柱就彈出頂端。目前索引是被彈柱子的第一個無效位置，所以它的最大面積是 bar.height * (right - bar.start)。我把它的起點傳給目前高度，因為這根更矮柱可以覆蓋剛移除 的所有高柱。目前高度與堆疊頂端相等時保留更早項，不再重複推入。最後用一根虛擬零高柱關閉 剩餘後綴。

堆疊不變量保證每個堆疊項從起點到目前位置之前的柱子都足夠高，目前更矮柱則讓它的右邊界最終 確定。每個堆疊項最多被推入、彈出一次，所以時間為 O(n)，最壞空間為 O(n)。我會測試相等 高度、遞增與遞減陣列、零高度、擴充約定下的空輸入，並用平方級基準比對隨機小陣列。」

常見錯誤

每個錯誤都有具體原因和修正方式：

• 彈出後使用 right - start + 1 → right 已是第一個無效位置 → 應使用 right - start。
• 忘記最終清空堆疊 → 遞增後綴從未計算 → 多掃描一根虛擬零高柱。
• 每個相等高度都推入 → 正確性依賴更細緻的彈出規則 → 保留最早的同高堆疊項。
• 認為內層迴圈導致平方時間 → 每個堆疊項只能彈出一次 → 給出攤銷次數。
• 把哨兵附加到 heights → 呼叫端觀察到輸入被修改 → 虛擬計算哨兵。

追問深入

追問一：如何回傳矩形邊界？

每當面積變大時，同時保存 { start: bar.start, end: right - 1, height: bar.height }。編碼前要 先定義並列規則：優先最靠左、最寬，還是最高的矩形。面積相同並不能唯一確定答案。

追問二：柱子寬度可變怎麼辦？

用物理寬度的前綴和取代索引差。堆疊項需要保存最早水平座標，彈出時的面積變為 height * (currentX - startX)。零寬柱和非法負寬度都需要明確介面約定。

追問三：如何擴充到二進位矩陣？

把每一列當作直方圖底邊。目前格為 1 時累加該欄高度，為 0 時清零；每處理一列就執行一次 直方圖演算法。對 m × n 矩陣，時間為 O(mn)，輔助空間為 O(n)。

追問四：資料以串流形式到達時能否維護精確答案？

堆疊可以在線接收柱子，但串流右端仍開放的矩形尚未最終確定。需要快照時，可以用目前長度計算 這些堆疊項的臨時面積而不彈出。嚴格遞增串流會讓精確狀態增長到 O(n)；從這個不變量無法得到 固定記憶體的精確演算法。

追問五：輸入大到單機記憶體放不下怎麼辦？

只計算每個分塊內部最大值不夠，因為獲勝矩形可能跨越分塊邊界。分散式摘要必須保留足夠的邊界 高度結構才能合併相鄰區塊，而單調區塊的邊界結構本身可能是線性的。承諾常量大小摘要前，應先 說明這個下界風險。

追問六：什麼時候更適合其他方案？

平方級基準最適合小輸入驗證。圍繞最小值做分治有助於推導遞迴關係，但每層線性尋找最小值會在 有序輸入上退化到 O(n^2)。區間最小值資料結構適合還要處理其他重複查詢的場景；只求一次靜態 最大面積時，單調堆疊更簡單，並達到漸近最優。