給定一個整數陣列
heights代表直方圖中各柱子的高度（每個柱子寬度為 1），找出直方圖中能勾勒出的最大矩形面積。
Example:
Input: heights = [2,1,5,6,2,3] Output: 10
Intuition
TIP
核心思路：對每根柱子，找出它能向左右延伸的最大範圍（即左右第一個比它矮的柱子），面積 = 高度 x 延伸寬度。用單調遞增堆疊可以 O(n) 完成。
- 以每根柱子的高度作為矩形的高度，寬度取決於向左右能延伸多遠
- 暴力法對每根柱子向左右掃描找邊界，O(n^2)
- 單調遞增堆疊：當遇到更矮的柱子時，棧頂柱子的「右邊界」確定了（就是當前位置），「左邊界」就是棧中前一個元素
Approaches
1. Brute Force (expand per bar) — O(n^2) / O(1)
- Idea: 對每根柱子，向左右擴展直到遇到更矮的柱子，計算面積
- Time:
O(n^2)- 每根柱子最壞擴展 O(n) - Space:
O(1)
class Solution {
fun largestRectangleArea(heights: IntArray): Int {
var maxArea = 0
for (i in heights.indices) {
var left = i
var right = i
while (left > 0 && heights[left - 1] >= heights[i]) left--
while (right < heights.size - 1 && heights[right + 1] >= heights[i]) right++
maxArea = maxOf(maxArea, heights[i] * (right - left + 1))
}
return maxArea
}
}⭐ 2. Monotonic Stack — O(n) / O(n)
- Idea: 維護遞增單調堆疊（存索引）。遇到比棧頂矮的柱子時，彈出棧頂並計算以其高度為高的矩形面積。遍歷結束後清空堆疊中剩餘元素
- Time:
O(n)- 每個元素最多入棧出棧各一次 - Space:
O(n)- 堆疊空間
class Solution {
fun largestRectangleArea(heights: IntArray): Int {
val stack = ArrayDeque<Int>() // 存索引
var maxArea = 0
val n = heights.size
for (i in 0..n) {
val currentHeight = if (i == n) 0 else heights[i]
while (stack.isNotEmpty() && currentHeight < heights[stack.last()]) {
val height = heights[stack.removeLast()]
val width = if (stack.isEmpty()) i else i - stack.last() - 1
maxArea = maxOf(maxArea, height * width)
}
stack.addLast(i)
}
return maxArea
}
}Note: Prefix/Suffix Arrays
預計算每根柱子的左邊界（左側第一個比它矮的位置）和右邊界（右側第一個比它矮的位置），再逐柱計算面積。
class Solution {
fun largestRectangleArea(heights: IntArray): Int {
val n = heights.size
val leftBound = IntArray(n)
val rightBound = IntArray(n)
// 計算左邊界
leftBound[0] = -1
for (i in 1 until n) {
var p = i - 1
while (p >= 0 && heights[p] >= heights[i]) {
p = leftBound[p]
}
leftBound[i] = p
}
// 計算右邊界
rightBound[n - 1] = n
for (i in n - 2 downTo 0) {
var p = i + 1
while (p < n && heights[p] >= heights[i]) {
p = rightBound[p]
}
rightBound[i] = p
}
var maxArea = 0
for (i in 0 until n) {
maxArea = maxOf(maxArea, heights[i] * (rightBound[i] - leftBound[i] - 1))
}
return maxArea
}
}- Time:
O(n)- 每個邊界計算是均攤 O(1) - Space:
O(n)- 兩個邊界陣列
WARNING
巧妙技巧：在遍歷結束時加一個高度為 0 的「虛擬柱子」（i == n 時 currentHeight = 0），確保堆疊中所有剩餘元素都被處理。寬度計算 i - stack.last() - 1 在棧空時代表從位置 0 到 i，即寬度為 i。
🔑 Takeaways
- Pattern: 「找每個元素左右第一個更小值」= 單調遞增堆疊的經典應用
- Key trick: 在陣列末尾加虛擬元素（sentinel）清空堆疊是常見技巧；寬度計算需理解「棧中前一個元素就是左邊界」的含義。此題是許多進階題（如 85. Maximal Rectangle）的基礎