LeetCode - 84. 柱狀圖中最大的矩形_Pseudocode

小知識，大挑戰！本文正在參與“程序員必備小知識”創作活動。

原題：84. 柱狀圖中最大的矩形

給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。

求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。

如上圖，最終結果的矩形就是圖中的紅色矩形，它的面積是 10。

解題思路：

根據上圖，最容易想到的辦法，就是暴力求解：遍歷數組中的每一個元素，然後一這個元素為起點，分別向左和向右眼神，知道遇到比這個元素低的柱子，那麼就找到了一個高度為當前元素高度、寬度為左右延伸距離之和加元素本身的1個寬度的矩形。通過對每個元素都進行這樣的運算，邊計算邊比較，就可以得到最大的值。

這個方法相當於對數組進行了兩層遍歷，時間複雜度為 O(n^2)。我們需要找到優化的空間，以上解法的問題是，在遍歷數組的過程中，很多數據沒有留存，導致每遍歷到一個元素都需要在整個數組尋找當前元素高度可以勾勒的巨型面積的寬度。我們可以通過空間換時間的方式，記錄遍歷過程中的數據，實現時間複雜度的優化。

首先，還是從頭到尾遍歷數組，在遍歷的過程中確定當前元素高度可以勾勒的矩形的左右邊界。

以開頭的圖為例，當遍歷到下標為 0 的柱子，高度為 2，因為它左邊沒有其他元素，因此它的左邊解釋確定的，但是因為還不知道後面柱子的高度，因此右邊界還無法確認。接着遍歷到下標為 1 的柱子，高度是 1，比 2 小，此時，高度是 2 的柱子能勾勒的矩形的右邊界就確認了。此時，就不需要在考慮高度是 2 的那個柱子。

但是高度是 1 的柱子的右邊界依然不確定，需要接着向後遍歷。通過不斷重複以上向後遍歷和高度比較的過程，我們可以發現，假設當前便利到的柱子下標是 curr，當下標是 curr + 1 的柱子比 curr 更高的時候，我們無法確定 curr 的右邊接，但是當它更低的時候，之前的比 curr + 1 更高的所有柱子的右邊界就都確認了。

因此，在我們便利柱子高度的過程中，如果 curr + 1 比 curr 更高，我們就記錄下來，如果更低，那麼就從之前記錄的高度中尋找它的左邊界，當 curr 的高度所能勾勒出來的矩形被確認並計算出它的面積之後，就從我們記錄的數據中清除。

這樣我們記錄的所有柱子，他們的高度就是遞增的。（便利的過程中，如果柱子不斷變高就記下來，如果變低，就找出前面更高的柱子，計算他們對應的結果，並清楚），並且，更後記錄的柱子，會更早地確認矩形的面積，也就是後進先出。因此，我們記錄數據的數據結構是一個單調的棧。

最後，當便利完所有元素，並計算出以他它們的高度能勾勒出的矩形的面積之後，最終得到過程中比較出的最大值。

另外，由於過程中需要對頭尾的元素進行判斷做不同的邏輯處理，為了簡化運算，我們可以在數組頭尾各加入一個高度為 0 的柱子，這樣可以免去判斷的麻煩，且不影響結果。

最終代碼：

java class Solution { public int largestRectangleArea(int[] heights) { int n = heights.length; if (n == 0) { return 0; } if (n == 1) { return heights[0]; } int[] newHeights = new int[n + 2]; System.arraycopy(heights, 0, newHeights, 1, n); heights = newHeights; n += 2; int max = 0; Deque<Integer> stack = new LinkedList<>(); stack.push(0); for (int i = 1; i < n; i++) { while (heights[stack.peek()] > heights[i]) { int h = heights[stack.pop()]; while (!stack.isEmpty() && heights[stack.peek()] == h) { stack.pop(); } int w = i - stack.peek() - 1; max = Math.max(max, w * h); } stack.push(i); } return max; } }