84. Largest Rectangle in Histogram

這題是hard, 也真的蠻難的, 我們在看完網路上解答後, 慢慢分析

首先是第一種做法, 第一種做法要做的我們只看當前”較高”的幾根柱子, 何謂較高, 就是大於你後面那根柱子的高度, 就是較高

接著, 我們針對這些柱子, 幫他們去往回掃描, 往回找到最低的柱子, 並且看區域面積有沒有比較大, 到結束

這個就很不好想了其實, 為什麼可以只考慮這些”較高”的柱子?

因為較高的柱子可以去接納低柱子, 我們往前回看也都是找最低的, 所以這樣做一定可行

但是, 這個方法速度太慢了, 時間複雜度為O(n²), 在leetcode會time limit

class Solution {
  public:
    int largestRectangleArea(vector<int> &heights) {
        int res = 0;
        for (int i = 0; i < heights.size(); i++) {
            if (i + 1 < heights.size() && heights[i] <= heights[i + 1]) {
                continue;
            }
            int minH = heights[i];
            for (int j = i; j >= 0; j--) {
                minH = min(minH, heights[j]);
                int area = minH * (i - j + 1);
                if (area == 0) {
                    break;
                }
                res = max(res, area);
            }
        }
        return res;
    }
};

這題的tag 有stack, 所以我們下個目標就是來想stack要怎麼運用

其實這會用到類似於第一題的概念, 只是他的用法更具巧思, 首先, 我們會準備一個遞增的stack, 從頭開始往裡面疊放, 倘若發現當前高度(C)已經小於stack裡最上方的高度, 我們就要出來做一次清算

有沒有發現, 這跟方法一有哪裡像, 一樣就是找到較高的柱子進行處理,

我們會取出目前stack裡面最上層的柱子(A), 開始做計算, 他可以直接針對stack內後來最上層的柱子(B)去做計算, Why, 上面是要掃遍全部位置小於這個柱子, 怎麼這邊只需要針對stack裡的項目去做就行了？

原因是後面留有一個巧思, 我們會在陣列最後面補一個0, 強制去輸出剩下留在stack裡的所有柱子, 他只抓次高的(B), stack再下去, 就會降低高度, 整個要重來, 所以補0強制輸出這招蠻猛的, 等於是所有剩餘柱子一定都小於0, 直接清空

最後記得在每次清算完, 要把剛剛在計算前的柱子(C) 再推回去, 不然他就被遺忘了,把index往前減回去, 讓下一次再重新考慮他

最後(st.empty() ? i : (i — st.top() — 1)), 這段code是在做什麼呢？

會有一種case是

[1], [1,1,1,1]

上面的case我們並無法用這個方式檢查到, 因為當前的stack為空的, 我們可以判定, 當前的cur_index即是這個段落的最小值, 所以他可以直接乘以i

補上code

class Solution {
  public:
    int largestRectangleArea(vector<int> &heights) {
        int res = 0;
        stack<int> st;
        heights.push_back(0);
        for (int i = 0; i < heights.size(); ++i) {
            if (st.empty() || heights[st.top()] < heights[i]) {
                st.push(i);
            } else {
                int cur = st.top();
                st.pop();
                res = max(res,
                          heights[cur] * (st.empty() ? i : (i - st.top() - 1)));
                i--;
            }
        }
        return res;
    }
};