今天要講的是leetcode84題，柱狀圖中最大的矩形，題目鏈接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
題目大意：給你一個陣列，陣列中的每個數都對應的是高度，你把他想象成一個柱狀圖，每個柱子的寬度都是1，你來求他形成的最大矩形的面積，就以示例來說，給你的陣列為[2,1,5,6,2,3]，你可以想象成這個樣子
很明顯，矩形的最大面積是這樣的
你可以列舉其他的情況，但是會發現都不如這個大，矩形的面積是高乘寬，所以我們要求的面積不僅只是和高度有關，還和寬度有關，即使heights[3]=6比heights[2]=5要來得大，但是由于5的寬度可以向右擴展到6這邊，所以5乘上2要大于6乘上1，因此最大的面積是以heights[2]為高的，
說到這里，我們就可以想到可以以每個heights[i]為高一一列舉，看看他們能到達的最大左邊界和右邊界，就是這個寬，然后再乘以高度就得到了面積，最后取最大值就可以得出答案，就比如heights[2]它最遠的左邊界就是2他自己，因為它左邊的數[2,1]都比他小，因為我們不能缺胳膊斷腿，這樣就不是矩形了，而右邊界可以達到3，因為6比5大，我們可以只取6中的5高度來使得我們的寬度變大，簡單的來說，就是我們以一個heights[i]為高度中心，來找出左邊和右邊第一個比他小的邊界在哪里，
先來看代碼：
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n=heights.size();
if(n==0)
return 0;
int left[n];
int right[n];
stack<int> l;
for(int i=0;i<n;i++){
while(!l.empty()&&heights[i]<=heights[l.top()])
l.pop();
if(l.empty())
left[i]=-1;
else
left[i]=l.top();
l.push(i);
}
stack<int> r;
for(int i=n-1;i>=0;i--){
while(!r.empty()&&heights[i]<=heights[r.top()])
r.pop();
if(r.empty())
right[i]=n;
else
right[i]=r.top();
r.push(i);
}
int ret=0;
for(int i=0;i<n;i++){
ret=max(ret,heights[i]*(right[i]-left[i]-1));
}
return ret;
}
};
這里用到的資料結構還是單調堆疊，使用的演算法思想就是預處理，這個預處理比較簡單，只要處理完成就可以直接得出答案，
我們left陣列就是以i為高度左邊最遠能到達的下標，例如[-1,1,1]，對于下標2來說，我們左邊最遠能到達1這個下標，注意我這邊說的左邊最遠到達和右邊最遠到達都是左開右開的開區間，就比如一個下標 i 左邊可以到達-1，右邊可以到達4，所以它的范圍應該是(-1,4)，并不是閉區間，所以最后求答案的時候，它的寬度應該是右邊界-左邊界-1，即4-（-1）-1=4.
之所以使用單調堆疊，就是因為每個高度的左邊和右邊都有一個瓶頸，例如[3,2,4,5]，對于4這個高度來說，它左邊的瓶頸就是2，因為2<4，我們單調堆疊中從堆疊頂到堆疊底的元素應該是遞減的，這是因為如果2不是左邊的瓶頸的話，那么3就一定不是左邊的瓶頸，因為3>2，
有意思的是，我們存入堆疊的元素是下標，而比較的時候是用heights這個陣列來進行比較，這個地方比較巧妙，
我們來模擬一下這個程序：還是題目給我們的例子[2,1,5,6,2,3]，我就單單以左邊界舉例
1)i=0，我們的堆疊為空，所以0入堆疊，left[0]=-1,意思就是2這個高度，它能到達的最遠左邊界為-1；
2)i=1,1<2所以0出堆疊，left[0]=-1,1入堆疊，此時堆疊中元素只有1，千萬不要給繞暈，堆疊中的元素是下標；
3)i=2,5>1，left[2]=1，2入堆疊，堆疊中元素[1,2];
4)i=3,6>5, left[3]=2,3入堆疊，堆疊中元素[1,2,3];
5)i=4,2<6,3出堆疊，2<5,2出堆疊，left[4]=1，4入堆疊，堆疊中元素[1,4]；
6)i=5,3>2,left[5]=4,5入堆疊；
至此，我們就已經預處理完left這個陣列，這樣就可以知道任意一個高度它左邊界是哪兒了，同樣的方法我們可以完成right這個陣列，區別就是我們需要從右往左遍歷，
還有一個值得注意的地方是，就算當前的高度和堆疊頂的高度一樣高，我們照樣還是需要將堆疊頂的元素pop出來，舉個例子：[2,2,3]，對于3來說，它左邊的瓶頸就是2，如果我們不將堆疊頂的元素進行更新的話那么堆疊頂保留的下標是0，換句話說，就是3的瓶頸不是下標為1的2，而是下標為0的2，這樣求出來的面積是（（3-0）-1）*3=6，這顯然是不符合這個事實的，
好啦，至此這道題的細節我都講完啦，喜歡的可以點個贊哦，
繼續加油：）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/260613.html
標籤：其他
上一篇：實作紅綠燈的效果