acwing 131.直方圖中最大的矩陣

acwing 131.直方圖中最大的矩陣

算法：（數組模拟棧+單調棧）

思路：

1.首先先思考最大矩形的特點，一定是以某個矩形i的高為最大矩形的高，然後以這個矩形i往兩邊擴充而來的最大矩形；是以想到暴力做法就是周遊i，每個矩形i往兩邊擴充出一個以矩形i的高為高的最大矩形，是以，然後更新答案，周遊完成之後就得到最終答案。

2.暴力的思路看看n的範圍10^5如果雙重循環就TLE了，是以想着怎麼去優化它；比如對矩形i往左邊擴充是，如果擴充到左邊的一個比較矮矩形，那麼，更左邊更高的矩形就被限制住了，不會拿來構成最大矩形，是以就不會存在遞減序列。聯想到單調棧，假設我們維護了一個單調遞增棧，矩形i就能尋找到距離它最近的比它矮的矩形下标j，那麼j到i之間的都是和矩形i等高或者更高的矩形，自然就能構成最大矩形；右邊同理

3.向左和向右都要維護一個單調棧，然後記錄距離它最近的比它矮的矩形下标，就要l和r的兩個數組來存

4.每個矩形高大于等于0，矩形标号從1~n，是以在邊界的時候很容易越界過去，比如矩形i往左尋第一個比它矮的矩形時，可能尋找下标1，但是此時萬一下标1的矩形高等于0，那麼棧彈出的時候會因為0号位好似有個矩形高為0，把它彈出，就會繼續向左好像尋找到數組裡0标号的高度預設為0的矩形，但其實沒有這個矩形，那麼就會尋找錯誤；因為這種情況的存在，是以我們直接在左邊界更左邊0号位放置一個-1高的矩形，在右邊界更右邊n+1号位放置-1高的矩形，這樣就不會尋找左右邊界的時候超出去了

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+5;

typedef long long ll;

int h[N],l[N],r[N];	//l記錄往左尋的最靠近矩形i的比它矮的矩形标号，r記錄往右尋的靠近矩形i的比它矮的矩形标号
int stk[N];	//拿來維護單調棧的模拟數組，記錄下标 
int main ()
{
	int n;
	while (cin>>n,n)
	{
		for (int i=1;i<=n;i++) cin>>h[i];
		
		h[0]=h[n+1]=-1;	//防止尋找下标越界 
		
		
		stk[0]=0;	//因為設定了一個-1高的0号矩形，是以提前入棧0标号 
		int tt=0;	//棧0号位已經有東西了，是以tt從0開始 

		for (int i=1;i<=n;i++)
		{
			while (h[stk[tt]]>=h[i]) tt--;	//已經入棧了初始标号，是以不用判斷棧非空；遇到非遞增，就彈出棧頂 
			l[i]=i-stk[tt]-1;		//l數組記錄矩形i到棧頂記錄的标号之間有多少個比矩形i更高或者等高的矩形 
			stk[++tt]=i;
		}
		
		
		stk[0]=n+1;	//因為設定了一個-1高的n+1号矩形，是以提前入棧n+1标号
		tt=0;		//同上 
		
		for (int i=n;i>=1;i--)	//注意這裡是從n号位開始到1号位了 
		{
			while (h[stk[tt]]>=h[i]) tt--;
			r[i]=stk[tt]-i-1;		//同上 
			stk[++tt]=i;
		}
		
		ll ans=0;	//寬是10^5數量級，高是10^9數量級，10^5*10^9會爆int，是以用long long，下面的潛質類型轉換也是為了防止爆int 
		for (int i=1;i<=n;i++) ans=max(ans,(ll)(l[i]+r[i]+1)*h[i]);	//答案更新；然後寬的時候要加上1，因為還有矩形i本身也算一個 
		cout<<ans<<endl;
	}
	return 0;
}