柱狀圖中最大的矩形
原題：84. Largest Rectangle in Histogram
題目描述：
給定\(n\)個非負整數，用來表示柱狀圖中每個柱子的高度，每個柱子相鄰且寬度為1，
求這個柱狀圖中能容納的最大矩形的面積，
思路：
對于一個柱狀圖中的最大矩形，我們可以觀察出如下性質：
- 矩形的高必等于某個柱子的高度，也就是矩形的上邊與某個柱子的上邊在同一條直線上，
證明：假設上述不成立，那對于每個柱子，它們的高都比這個最大矩形的高至少大1，因此我們可以增加這個矩形的高，得到一個更大的矩形，并且這個矩形還在柱狀圖中，因此這個矩形不是最大的矩形，得出悖論，因此此條性質成立， - 矩形的左邊柱子的高度小于矩形高度，矩形的右邊柱子的高度小于矩形的高度，
證明：顯而易見，如果左右兩邊的柱子高度大于等于矩形的高度，那么就可以向左右延伸矩陣，得到一個更大的矩陣，
根據上面兩個性質，我們可以得出一個求最大矩陣的演算法：
演算法：
對于每一個柱子\(i\)，如果我們知道它左邊和右邊第一個比它矮的柱子的位置\(left,\ right\)，我們就可以計算出以這個柱子\(i\)為頂邊的最大矩形，其面積為\((right-left-1)\times height[i]\)，
對于每個柱子都進行上述計算，取其中的最大值，即為整個柱狀圖中的最大矩形，
那如何求每個柱子左右兩邊第一個比它矮的柱子位置呢？可以拆解為兩個問題：1. 找到每個柱子右邊第一個比它矮的柱子的位置，2. 找到每個柱子左邊第一個比它矮的柱子的位置，
像這樣具有單調性的題目，應該使用單調堆疊解決，下面演示單調遞增堆疊的細節，
單調堆疊(單調遞增堆疊)
記一個陣列\(right\)，大小為\(n\)即總元素的個數，用來記錄每個\(index\)對應的右邊的第一個小于\(height[index]\)的元素的\(index'\)，我們將其初始化為\(n\)，即默認右邊第一個小于\(height[index]\)的元素的位置為\(n\)，
維護一個堆疊(存的是元素的index)，對于每一個新元素\(a\)，如果大于等于堆疊頂元素，直接把其index push進堆疊；如果比堆疊頂元素小，把堆疊頂元素對應的\(right[i]\)設為\(a\)的\(index\)，再對堆疊進行pop操作，如此反復直到\(a\)大于等于堆疊頂元素，再把其index push進堆疊，回圈完了，如果堆疊中還剩下元素，這些元素的右邊沒有比它們小的元素，于是就默認為\(n\)了，
通過上述程序我們可以得到每個柱子右邊第一個比它矮的柱子的位置，同理可以得到每個柱子左邊第一個比它矮的柱子的位置，但是通過觀察可以發現：每個元素的index在被push進入堆疊的時候其左邊界就可以“確定了”：為堆疊頂的index，解釋如下：
如果堆疊中沒兩個相鄰的元素的高不同，我們在進行push進堆疊的時候，堆疊頂的元素的值已經小于我們將push進去元素的值了，因此每個元素在被push的時候左邊界就確定了，為堆疊頂的值，
如果堆疊中有高相同的元素相鄰，如\(a,b:height[a]=height[b],a<=b\)，采用上述方法的，\(b\)的左邊界值就不準確了，因為其左邊界值被設定為\(a\)，但其實\(height[a]=height[b]\)，\(b\)的真實左邊界值其實應該比\(a\)小，以柱子\(b\)為頂邊的矩形的面積就不是最大的，因為這個矩形還能向左延伸，那怎么辦呢？
其實這樣的不準確并不影響求以\(a\)或\(b\)為上邊的矩形的面積，既然\(height[a]=height[b]\)，并且它們在堆疊中相鄰，說明它們中間沒有比它們小的值，對于元素\(a\)，其左邊界是準確的，即\(height[left[a]]<height[a]\)，并且以柱子\(a\)為頂邊的矩形包含了以柱子\(b\)為頂邊的矩形，所以即使堆疊中在\(a\)上面還有很多元素，其柱子高度等于柱\(a\)的高度，并且它們的左邊界都不準確，只要同高的最左元素\(a\)的左邊界正確就能確定它們包圍的矩形的最大面積，
所以我們可以在求右邊界的時候就可以確定左邊界的位置，
詳細代碼如下：Java
class p84 {
public int largestRectangleArea(int[] heights) {
int n = heights.length, maxSize = 0;
Deque<Integer> mono_stack = new ArrayDeque<Integer>();
int[] left = new int[n];
int[] right = new int[n];
Arrays.fill(right, n);
for (int i = 0; i < n; i++) {
while (!mono_stack.isEmpty() && heights[mono_stack.peek()] > heights[i]) {
right[mono_stack.peek()] = i;
mono_stack.pop();
}
left[i] = mono_stack.isEmpty() ? -1 : mono_stack.peek();
mono_stack.push(i);
}
for (int i = 0; i < n; i++) {
maxSize = Math.max(maxSize, (right[i] - left[i] - 1) * heights[i]);
}
return maxSize;
}
}
復雜度分析：
空間復雜度：使用兩個陣列存左右邊界，復雜度為\(O(n)\)，
時間復雜度：遍歷每個元素為\(n\)，在遍歷中進行pop、push等操作，但是pop和push的總操作量小于\(O(2n)\)，最后遍歷計算最大面積\(O(n)\)，因此總時間復雜度為\(O(n)\)，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/457594.html
標籤：其他
下一篇：【課程筆記】中科大資訊論（六）