LeetCode力扣84.柱狀圖中最大的矩形
題目描述
給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度，每個柱子彼此相鄰，且寬度為 1 ，求在該柱狀圖中，能夠勾勒出來的矩形的最大面積，
輸入輸出樣例
輸入 #1
6
2 1 5 6 2 3
輸出 #1
10
解釋：最大的矩形為圖中紅色區域，面積為 10
解題思路
首先第一眼可以看出本題用暴力法一定可以做出來，但純暴力一般會超時，可以借助單調堆疊對暴力法進行優化，
先說暴力法，最外層回圈遍歷 n 根柱子，內部對每根柱子左右分別進行 while 回圈找到第一根高度小于當前高度的柱子，就可以算出以當前柱子為高時矩形的最大面積，遍歷結束即可找出矩形最大面積，
單調堆疊法，依舊是最外層回圈遍歷 n 根柱子，并且只在堆疊中存盤高度遞增的柱子的陣列下標，比如第 i 根柱子的高度大于堆疊頂的柱子高度時，就讓i入堆疊，小于堆疊頂柱子高度，說明以堆疊頂為高的矩形找到了右邊界，而堆疊中存盤的是遞增的序列，那么左邊界也確定了，左右邊界做差就得到了矩形的寬，那么以堆疊頂為高的矩形的最大面積就確定了，將面積與之前記錄的最大面積進行比較，更新最大面積，遍歷結束就得到了最終結果，這樣就省去了純暴力中每次回圈查找左右邊界的程序，光看文字看不懂，這里建議看代碼畫圖自己模擬一遍，
要注意的是最外層遍歷要多執行一次,for(int i=0;i<=n;i++)，下標為 n 的陣列中存柱子高度為0，因為如果出現 n 根柱子高度恰好為遞增序列的情況，那么程式不會對最大面積進行更新，
代碼
此代碼不支持上機檢測，
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
int n; //柱子數量
int max_area; //記錄當前最大面積
int area; //記錄以當前柱子為高的最大面積
int height[100005]; //存盤柱子高度
stack<int> s; //存盤高度遞增的柱子的陣列下標
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>height[i];
for(int i=0;i<=n;i++)
{
while(!s.empty()&&height[s.top()]>height[i]) //堆疊非空且第i根柱子高度堆疊頂柱子高度，此時不能入堆疊，開始計算面積
{
if(s.size()==1) area=height[s.top()]; //當堆疊中僅有一個元素，矩形高為柱子高度寬為1
else area=height[s.top()]*(i-s.top()); //當堆疊中有多個元素，矩形高為堆疊頂柱子高度，寬為左右第一個比當前柱子矮的兩柱子的間距即i-s.top
max_area=max(max_area,area); //與之前記錄的最大面積作比較，更新最大面積
s.pop(); //已做過高的柱子出堆疊
}
s.push(i); //堆疊慷訓者堆疊頂柱子高度小于第i根柱子高度，下標入堆疊
}
cout<<max_area;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/421640.html
標籤：其他