單調堆疊

目錄

名詞解釋

實作

功能

例題

名詞解釋

要了解什么是單調堆疊，我們可以分開來理解一下什么叫“單調”，什么叫“堆疊”，

堆疊

先引入百度百科中堆疊的定義

堆疊（stack）又名堆疊，它是一種運算受限的線性表，限定僅在表尾進行插入和洗掉操作的線性表，這一端被稱為堆疊頂，相對地，把另一端稱為堆疊底，向一個堆疊插入新元素又稱作進堆疊、入堆疊或壓堆疊，它是把新元素放到堆疊頂元素的上面，使之成為新的堆疊頂元素；從一個堆疊洗掉元素又稱作出堆疊或退堆疊，它是把堆疊頂元素洗掉掉，使其相鄰的元素成為新的堆疊頂元素，

用自己的話來說，堆疊是一種資料結構，其主要特點就是先進后出，

堆疊的具體操作這里就不細講，

單調

小學五年級的學生都知道單調是什么意思，

一個遞增的函式，被稱為是單調遞增函式；一個遞減的函式，被稱為是單調遞減函式，而兩者統稱為單調函式，

而在這里，單調指的就是遞增或遞減，

單調堆疊

那么合起來，單調堆疊則是指這個堆疊內的元素單調，從底部到頂部要么單調遞增，要么單調遞減，

實作

要實作一個單調堆疊其實特別簡單，以單調遞增的堆疊為例子：

假設現在有7個元素，分別為6 9 7 9 10 4 8，

那么首先進入堆疊里的是元素6，先入堆疊，

然后是元素9,9>6，因為建立的是一個單調遞增的堆疊，所以9也入堆疊，

然后進來了一個7，由于7比9小，為了形成一個單調遞增的堆疊，則需要把9去掉，

然后堆疊內還有6，7比6大，為了形成一個單調遞增堆疊，所以直接讓7入堆疊 ，

那么現在已經堆疊內的情況為：

后面的元素9比7大，所以直接入堆疊，

然后的元素10比9大，所以也直接入堆疊，

然后堆疊內的情況就如下圖所示：

下一個元素是4,4先和堆疊頂的元素10比較，10比4大，所以10出堆疊，

然后再比較10出堆疊后的堆疊頂元素9，9仍然比4大，所以9出堆疊，

在比較此時的堆疊頂元素7，7還是比4大，所以7出堆疊，

隨后比較此時堆疊頂元素6，6比4大，所以也出堆疊，但此時堆疊已經為空，所以將4入堆疊，

然后再來一個元素8，8比堆疊頂元素4要大，所以8入堆疊，最后堆疊內情況如下圖所示

所以實作一個單調堆疊，其實無非就三步：判斷，出堆疊，入堆疊，

功能

那么知道如何實作一個單調堆疊以后，我們能用單調堆疊來做什么呢？

大家先思考一個問題，實作單調堆疊的時候，最重要的部分是哪？ 判斷是否能夠入堆疊使得堆疊內元素單調，

對的，我們需要操作的部分就是判斷，

當一個新的元素準備入堆疊時，我們與堆疊頂元素進行判斷，如果該元素入堆疊后使得單調性破壞，則我們的步驟則是不斷地讓堆疊頂元素出堆疊，直到新的元素入堆疊后繼續保持堆疊內元素的單調性，

而與堆疊頂元素破壞堆疊內元素單調性的這個矛盾，我認為便是單調堆疊功能的所在點，

這樣子的話，使用單調堆疊，就可以找到一段連續數列中破壞單調性的點，

例如在一組資料8 3 5 1 9中，需要你找到每個數左邊第一個比它大的數，

我們可以用最笨的方法，兩個for回圈，這樣子需要O（）的時間復雜度，

for(int i=1;i<n;i++)
{
    bool f=false;
    for(int j=i+1;j<=n;j++)
    {
        if(a[j]>a[i])
        {
            cout<<a[j]<<'\n';
            f=true;
            break;
        }
    }
    if(!f)
      cout<<0<<'\n';
}

很容易理解，用單調堆疊來實作的話，可以做到O（n）的時間復雜度，

我們建立一個單調遞減的堆疊，一直維護著單調遞減，當來了一個破壞單調性的元素時，也就是比堆疊頂元素大的元素，則開始比較，如堆疊頂的元素比新元素小，則這個新元素就是這個堆疊頂元素左邊的第一個比它大的數，然后這個堆疊頂元素就找到答案了，就出堆疊，然后再比較下一個堆疊頂元素，

用樣例8 3 5 1 9，一開始堆疊內維護著“8 3”，5比3大，則5是3左邊第一個比它大的元素，出堆疊，然后比較5和8，因為比5大的有可能比8大，并且要維持一個單調遞減的堆疊，則5入堆疊，1也類似，則此時堆疊內元素為“8 5 1”，當9要來時，9比此時的堆疊頂元素1大，9就是第一個比它大的數，然后1出堆疊，隨后比較5，最后比較8，都和元素1一樣的結果，所以最后就解決了問題，

這個問題也是洛谷里單調堆疊的模板題，

例題

洛谷P5788模板題

這題就是一個單調堆疊的模板題，找每個元素左邊第一個比它大的元素的下標，

#include<iostream>
#include<stack>
using namespace std;
const int oo=3000005;
int n,a[oo],f[oo];
stack<int> s;
void read_in()
{
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	  cin>>a[i];
	for(int i=1;i<=n;i++)
	  f[i]=i;
}
void work()
{
	for(int i=1;i<=n;i++)
	{
		if(s.empty() || a[s.top()]>a[i])
		  s.push(i);
		else
		{
			while(!s.empty() && a[s.top()]<a[i])
			{
				f[s.top()]=i;
				s.pop();
			}
			s.push(i);  
		 } 
	}
	while(!s.empty())
	{
		f[s.top()]=0;
		s.pop();
	}
	for(int i=1;i<=n;i++)
	  cout<<f[i]<<' ';
}
int main()
{
	read_in();
	work();
	return 0;
}

洛谷P2947

這題也是找左邊第一個比它高的牛，也是一樣的，

#include<iostream>
#include<stdio.h>
#include<stack>
using namespace std;
const int oo=100005;
int n,a[oo],ans[oo];
stack<int> s;
void read_in()
{
	ios::sync_with_stdio(false),cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	  cin>>a[i];
}
void work()
{
	for(int i=1;i<=n;i++)
	{
		if(s.empty() || a[s.top()]>=a[i])
		  s.push(i);
		else
		{
			while(!s.empty() && a[s.top()]<a[i])
			{
				ans[s.top()]=i;
				s.pop();
			}
			s.push(i); 
		  }  
	}
	for(int i=1;i<=n;i++)
	  cout<<ans[i]<<'\n';
}
int main()
{
	read_in();
	work();
	return 0;
}

SP1805

經典的矩陣面積覆寫問題，

這道題我們可以理解為，找以目前這個數為最小值，左邊第一個比它小的數的位置和右邊第一個比它小的數的位置，以這個數為最小值能組成的最大矩陣面積就是這兩者之間的距離為底，目前的數值為高的矩形的面積，然后再比較所有答案的最大值，

#include<iostream>
#include<stdio.h>
#include<stack>
using namespace std;
stack<int> s;
const int oo=100005;
int n;
long long l[oo],r[oo],a[oo],ans,A;
void read_in()
{
	ans=-1;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		l[i]=r[i]=i;
	}
}
void work()
{
	for(int i=1;i<=n;i++)
	{
		
		if(s.empty() || a[s.top()]<a[i])
		{
			s.push(i); 
		}
		else
		{
			while(!s.empty() && a[s.top()]>a[i])
			{
				l[i]=l[s.top()];
				r[s.top()]=i-1;
				s.pop();
			}
			s.push(i); 
		}
		
	}
	while(!s.empty())
	{
		r[s.top()]=n;
		s.pop();
	}
	for(int i=1;i<=n;i++)
	  ans=max(ans,(r[i]-l[i]+1)*a[i]);
	
}
int main()
{
	while(cin>>n)
	{
		if(n==0)
		  break;
		read_in();
		work();
		if(A!=0)
		  cout<<'\n';
		cout<<ans;
		A++;
	}
	
	return 0;
}

洛谷P1823

這題很讓我頭疼，因為這個涉及了新元素與堆疊頂元素相同時的處理問題，具體是什么問題大家可以做做看，我用STL的stack做超時最后幾個點了，然后找到了4年前自己還不會STL時用陣列模擬堆疊的程式，A掉了，下面貼超時的程式供大家思考和改進，（其實是我改不出2333希望有大佬撈我一把）

#include<iostream>
#include<stdio.h>
#include<stack>
using namespace std;
const int oo=500005;
stack<int> s;
int n;
long long a[oo],ans,same;
void read_in()
{
	ios::sync_with_stdio(false),cin.tie(0); 
	cin>>n;
	for(int i=1;i<=n;i++)
	  cin>>a[i];
}
void work()
{
	for(int i=1;i<=n;i++)
	{
		if(s.empty())
		{
			s.push(i); 
			continue;
		}
		if(a[s.top()]>a[i])
		{
			ans++;
			s.push(i); 
		}
		else
		{
			while(!s.empty() && a[s.top()]<a[i])
			{
				ans++;
				s.pop();
			}
			long long same=0;
			while(!s.empty() && a[s.top()]==a[i])
			{
				ans++;
				same++;
				s.pop();
			}
			if(!s.empty())
			  ans++;
			for(int j=1;j<=same;j++)
			  s.push(i); 
			s.push(i); 
		}
	}
	cout<<ans;
}
int main()
{ 
	read_in();
	work();
	return 0;
}

本人不才，單調堆疊只能稍微總結到這，如果有什么問題不懂，可以問問我，我會盡力回答，如果文章有什么問題或者我有表達錯的地方，也希望能夠指出，

謝謝大家，共同努力進步，