Largest Rectangle in Histogram

Question

Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Solution

這題難在數學，並不是說數學有多難，而是要想到很難。這題最 naive 的解法就是 for 開頭跟 for 結尾，接著找出這段之間最矮的木頭，進而算出所有 rectangle 後，再去比較誰最大。當然，這樣拿到的 time complexity 是 O(n³)。當然，這當中可以用一些優化去處理，但還是達不到最佳解。

在這題，我們可以觀察到，決定 rectangle 的面積其實是跟最矮的木頭有關，因此我們可以想到去 for 每一個木頭，把這個 for 到的木頭 (index = i) 當成最矮的木頭，然後往左往右看，如果找到一根比它短的木頭 (index = j)，那就代表能往那邊延伸 j - i + 1 的距離。

至於要怎麼用最佳解 O(n) 找到左右比它矮的木頭，就是屬於知道就知道，不知道就不知道的範疇 => 遞增 stack！！原理是我們把數字放進 stack 裡，由於是遞增的關係，因此我們可以知道，當前這個數字的前一個數字，就是它左邊第一個比它小的數。假如之後遇到一個數比當前這個數小，那我們又知道右邊第一個比它小的數。因此就可以在一次 iteration 的過程中，算出最大 rectangle。

在 implementation 過程中，有幾點必須小心：

1. 由於我們需要知道是 index 的距離，因此 stack 裡我們存的是 index，要求值的時候得用 nums[stack.pop()];

2. 要小心 corner case：當 index = nums.length 時，代表已經到底了，那我們可以放進一個 -1，接著之前所有數就可以陸續 pop 出來

3. 特別注意當 stack.isEmpty() 時，矩陣 width 的處理

    if (heights == null || heights.length == 0) {
            return 0;
        }

        Stack<Integer> stack = new Stack<Integer>();
        int max = 0;
        for (int i = 0; i <= heights.length; i++) {
            int curr = i == heights.length? -1 : heights[i];
            while (!stack.isEmpty() && curr <= heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty()? i : i - stack.peek() - 1;
                max = Math.max(max, height * width);
            }
            stack.push(i);
        }
        return max;