// poj 2559 Largest Rectangle in a Histogram 棧
// 
// n個(gè)矩形排在一塊，不同的高度，讓你求最大的矩形的面積(矩形緊挨在一起)
//
// 這道題用的是數(shù)據(jù)結(jié)構(gòu)做。也能夠遞推做。眼下僅僅會(huì)數(shù)據(jù)結(jié)構(gòu)的
//
// 對(duì)于每一個(gè)高度h，求一個(gè)左邊界L和右邊界R,分別表示的意義是
// L是下標(biāo)為j的矩形的高度的hj小于當(dāng)前h的最大的j的值。

則依據(jù)定義 // 我們能夠知道j到i之間的h都是大于當(dāng)前的hi的。 // R是下標(biāo)為k的矩形的高度的hk大于當(dāng)前h的最小的k的值。則依據(jù)定義 // 我們能夠知道i到k之間的h都是大于當(dāng)前的hi的。 // 則最后的結(jié)果就是max( ( R[i] - L[i] ) * h[i]). // // 詳細(xì)實(shí)現(xiàn)是用一個(gè)棧依次保存每一個(gè)矩形的高度。 // 設(shè)棧中的元素從上到下的值是x[i](x[i] > x[i+1] && h[x[i]] > h[x[i+1]]) // // 在計(jì)算L[i]的時(shí)候。當(dāng)棧頂元素j滿足h[j]>=h[i]時(shí)。一直出棧。直到j(luò)=0或者 // h[j] < h[i] 的時(shí)候，我們就求出了最大的h[j]>=h[i]的j的最小值即j+1 // // 在計(jì)算R[i]的時(shí)候，當(dāng)棧頂元素j滿足h[j]>=h[i]時(shí)，一直出棧。知道j=0或者 // h[j] < h[i] 的時(shí)候。我們就求除了最小的h[j]>=h[i]的j的最大值即j。 // // 所要注意的是 // // 計(jì)算L的時(shí)候要從左邊開始掃描,此時(shí)棧中須要的是1,2,...i的值 // 計(jì)算R的時(shí)候要從右邊開始掃描，此時(shí)棧中須要的是i+1...n的值 // // // 感悟： // // 從這道題中就能夠發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)棧的魅力的所在，個(gè)人感覺數(shù)據(jù)結(jié)構(gòu)非常奇妙， // 也更加篤定了我要學(xué)數(shù)據(jù)結(jié)構(gòu)的決心。

// // 繼續(xù)練 #include <algorithm> #include <bitset> #include <cassert> #include <cctype> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <vector> #define ceil(a,b) (((a)+(b)-1)/(b)) #define endl '\n' #define gcd __gcd #define highBit(x) (1ULL<<(63-__builtin_clzll(x))) #define popCount __builtin_popcountll typedef long long ll; using namespace std; const int MOD = 1000000007; const long double PI = acos(-1.L); const int maxn = 1e5 + 8; int a[maxn]; int st[maxn]; int n; int L[maxn]; int R[maxn]; void init(){ for (int i=0;i<n;i++) scanf("%d",&a[i]); int t = 0; for (int i=0;i<n;i++){ while(t>0 && a[st[t-1]]>=a[i]) t--; L[i] = t==0 ? 0 : st[t-1] + 1; st[t++] = i; } t = 0; for (int i=n-1;i>=0;i--){ while(t>0 && a[st[t-1]] >= a[i]) t--; R[i] = t==0 ? n : st[t-1]; st[t++] = i; } long long res = 0; for (int i=0;i<n;i++){ res = max(res,( R[i] - L[i] ) * (long long)a[i]); } printf("%lld\n",res); } int main() { //freopen("G:\\Code\\1.txt","r",stdin); while(scanf("%d",&n)!=EOF&&n){ init(); } return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/jzssuanfa/p/6814535.html

總結(jié)

以上是生活随笔為你收集整理的poj 2559 Largest Rectangle in a Histogram 栈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。