題目網址：https://leetcode.cn/problems/largest-rectangle-in-histogram/

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

返回柱狀圖中最大矩形的面積。

Solution 1：（TLE 無法通過）

想法：利用 Brute Force, 對於每一個 heights[i] 的寬度即為左、右邊第一個 < heights[i] 的位置, 其寬度為 right - left - 1 （left、right 都不包含在寬度中, 故要減一）

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int res = 0, n = heights.size();

        for (int i = 0; i < n; ++i) {
            // 找到左邊第一個 < heights[i] 的位置
            int left = i - 1;
            while (left >= 0 && heights[left] >= heights[i]) {
                --left;
            }

            // 找到右邊第一個 < heights[i] 的位置
            int right = i + 1;
            while (right < n && heights[right] >= heights[i]) {
                ++right;
            }

            // 中間的部分就是 area
            res = max(res, heights[i] * (right - left - 1));
        }

        return res;
    }
};
  • time：$O(n^2)$ ➔ for loop 中每一個 i 皆需 $O(n)$ 去找到左、右邊第一個 < heights[i] 的位置
  • space：$O(1)$ ➔ 只需常數空間

Solution 2：

想法：概念同 Solution 1, 利用 Monotonic Stack 來儲存 index, 維護一個遞增的 stack。一旦下一個元素 i 的高度比 stk.top() 的高度要小, 則可以知道 idx = stk.top() 的右邊高度比它小的第一個位置是 i, 而左邊高度比它小的第一個位置是把當前 stk.top() 給 pop 掉後的 stk.top()。stk 會不斷計算 idx = stk.top() 的 area, 並將 stk.top() 給 pop 掉, 直到 heights[stk.top()] < heights[i], 詳情請看這篇的方法二

e.g. stk = [1, 3]

  • 假設 idx = 4 的高度比當前 idx = stk.top() = 3 的高度要小, 則可以知道右邊第一個高度 < height[3] 的位置是 idx = 4
  • 此時我們想知道左邊第一個 < height[3] 的位置為何, 因此我們先將當前的 stk.top() 給 pop 掉, 此時 stk = [1], 然後取出 stk.top() = 1 為左邊第一個 < height[3] 的位置, 因為 stk 是遞增的, 所以將自己 pop 掉後的 stk.top() 必為左邊第一個比當前高度小的
  • 得到左、右邊第一個 < heights[stk.top()] 的位置後, 即可計算 idx = stk.top() 的面積

還要考慮 edge case 的情況：

  • 因為我們在取完當前 stk.top() 後將其 pop 掉後, 又取了一次 stk.top()。若 heights.size() = 1, 則 stk.size() = 1 會導致第二次取 stk.top() 時會出錯, 因此我們一定要有一個最低點在 heights 的起點, 這樣才能確保 stk.size() > 1
  • 除此之外, 我們還要保證 while loop 定會被執行, 因此我們一定要有一個最低點在 heights 的終點。否則, 當 heights 為遞增的, e.g. heights = [2, 4], 則 while loop 的條件 heights[stk.top()] > heights[i] 永遠不會成立, 會導致 res 不會被計算到
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int res = 0;
        stack<int> stk;

        // 考慮 edge case, 在 heights 前後加上高度為 0 的元素(最低點)
        heights.emplace(heights.begin(), 0);
        heights.emplace_back(0);

        for (int i = 0; i < heights.size(); ++i) {
            while (!stk.empty() && heights[stk.top()] > heights[i]) {
                const int height = heights[stk.top()];
                stk.pop();
                res = max(res, height * (i - stk.top() - 1));
            }
            stk.emplace(i);
        }

        return res;
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(n)$ ➔ stack 中的元素個數不超過 n