leetcode 題解 84. Largest Rectangle in Histogram （單調(diào)棧的應(yīng)用們）
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.
Above is a histogram where width of each bar is 1, given height =
[2,1,5,6,2,3].The largest rectangle is shown in the shaded area, which has area =
10unit.
圖片我就不貼了，大家自己腦補(bǔ)就好。
這個問題是歸類在stack題目分類下了。一開始我怎么看是怎么覺得這應(yīng)該是一個類似于線段樹的題目的，區(qū)間內(nèi)求最小值乘以區(qū)間長度這樣？
后來我發(fā)現(xiàn)discuss區(qū)有幾位大佬都是用棧去解決這個問題的，這就激發(fā)了我的好奇心，搜索了一番，發(fā)現(xiàn)了一種名為“單調(diào)棧”的套路。
單調(diào)棧，顧名思義，就是棧維持某種單調(diào)性，比如遞增、遞減、遞不增、遞不減。那么加入我有一個數(shù)組，要壓棧，要實現(xiàn)這種單調(diào)性，怎么破？有以下兩種思路：
- 當(dāng)要壓棧的數(shù)不滿足規(guī)定的單調(diào)性，就不把這個數(shù)壓棧。
- 當(dāng)壓棧的數(shù)破壞了單調(diào)性，就不停地彈出棧中的元素，直到新數(shù)字壓進(jìn)去也不會破壞單調(diào)性為止。這么說可能有點繞，舉個例子，比如我要在一個單調(diào)遞增的棧中壓入新數(shù)字3，而棧頂元素是4，此時直接壓入3就不是單調(diào)棧了，這時候我就彈出4，看新的棧頂元素，以此類推，直到棧頂元素小于3為止。
方法一按下不表，單看方法二，還是有很多用途的。最大的用途可以總結(jié)為：我可以找到數(shù)組中每一個特定數(shù)字后面會滿足/破壞某種條件的第一個元素。
來，請聽題：
給定一個數(shù)組，輸出一個與這個數(shù)組等長的數(shù)組作為結(jié)果。輸出的數(shù)組中的元素為，對于原數(shù)組中的第i個元素，需要往后移動多少個單位，才能找到第一個比他大的數(shù)字。如果沒有比他大的元素，該位輸出-1
這個時候，我們可以分析這個問題：
如果所有元素后面都沒有比他大的數(shù)字，那么這個數(shù)組就是一個單調(diào)遞減的數(shù)組。如果按順序把這個數(shù)組壓棧，則這個棧也就是一個單調(diào)遞減的棧。
那么如果我們構(gòu)造一個單調(diào)棧，假如，我是說假如，此時有一個元素插進(jìn)來，破壞了這個單調(diào)性，那么我們是不是可以認(rèn)為，就找到了第一個比相應(yīng)元素大的元素呢？
考慮一個測試?yán)?/p>
[9, 3, 5, 8, 2, 6]
實際上他還隱含了信息：位置。
我們可以寫成這樣：
[
<0, 9>,
<1, 3>,
<2, 5>,
<3, 8>,
<4, 2>,
<5, 6>
]
然后我們可以構(gòu)造一個單調(diào)遞減的棧，不同的是，我們在比較的時候使用值，但是在棧中存儲的卻是下標(biāo)，原因也很簡單，因為結(jié)果要的是距離，所以我們存下標(biāo)嘛。
ok，那我們開始壓棧了~
壓9，此時棧中元素為[0]，并且結(jié)果的數(shù)組是[-1, -1, -1, -1, -1, -1]
壓3，此時判斷9大于3，于是正常壓棧：[0, 1]
壓5，此時發(fā)現(xiàn)3小于5，單調(diào)棧的結(jié)構(gòu)要被破壞了，也就是說這個時候我們發(fā)現(xiàn)了比3大的第一個元素，于是出棧，并且可以更新3對應(yīng)的距離了，結(jié)果數(shù)組變成了[-1, 1, -1, -1, -1, -1]
以此類推：當(dāng)需要出棧的時候，就是更新結(jié)果之時，反之若一個下標(biāo)值一直沒有機(jī)會出棧，那么就說明從來沒有數(shù)比他要大。
那么寫成代碼大概可以是這樣的：
vector<int> findLarger(vector<int>& input) {
stack<int> tmp;
size_t len = input.size();
vector<int> output(len, -1);
for(int i = 0; i < len; i++) {
while(!tmp.empty() && input[i] < input[tmp.top()]) {
output[tmp.top()] = i - tmp.top();
tmp.pop();
}
tmp.push(input[i]);
}
return output;
}
看起來很簡潔是不？而且復(fù)雜度也只是O（n）。每個元素最多進(jìn)行一次入棧一次出棧。
OK，說完了單調(diào)棧的某些應(yīng)用，我們可以來看看Leetcode的84題了。
這個題目我們只需要分析清楚一件事就夠了：我們肯定是以某個矩形的頂為高來計算最大值的，所以我們只要想辦法計算出以每個矩形為頂矩形的面積并迭代即可。這時候我們可以考慮維護(hù)一個遞增的單調(diào)棧，當(dāng)需要出棧的時候，說明以該矩形為頂?shù)木匦蔚淖畲竺娣e已經(jīng)計算完畢了。（想想一下，如果右邊元素比左邊低了，那么左邊那個頂為高度的矩形肯定已經(jīng)無法向右邊延展了）這個時候可以計算一下矩形的值，并且更新一下max了。
寫成代碼大概是這樣的：
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
heights.insert(heights.begin(), 0);
heights.push_back(0);
stack<int> tmp;
int result = 0, sz = heights.size();
tmp.push(0);
for(int i = 1; i < sz; i++) {
while(heights[tmp.top()] > heights[i]) {
int h = heights[tmp.top()];
tmp.pop();
result = max(result, (i - tmp.top() - 1) * h);
}
tmp.push(i);
}
heights.erase(heights.begin());
heights.pop_back();
return result;
}
};
這樣就夠了。
這里用到討論區(qū)某個大佬的一個trick，向頭尾各插一個0進(jìn)去，可以保證棧內(nèi)有元素而省去一個判斷棧是否為空的步驟。
總的來說，單調(diào)棧看起來簡單，其實應(yīng)用場景很靈活，有時候都很難想到要去使用單調(diào)棧來解決問題，這個還是因為菜……需要多練習(xí)ORZ?？偟膩碚f，求取某個一二維數(shù)組的，滿足某種規(guī)則的極值，而這個極值還和相對位置強(qiáng)相關(guān)的時候，可以考慮使用單調(diào)棧解決。
