关键词：
单调栈
唠嗑：寒假遇到过，当时没能弄懂，昨天在算法进阶指南看到，再一次理解之后感觉对它的认识更近了一步，写一写记录一下，也理一下思路。
分类：
- 单调递增栈：单调递增栈就是从栈底到栈顶数据是从大到小
- 单调递减栈：单调递减栈就是从栈底到栈顶数据是从小到大
模板：
单调栈的题目解决的代码格式比较相似，下面是单调栈主体部分的模板。
伪代码：
stack<int> st;
//此处一般需要给数组最后添加结束标志符，一般在st的最后一个元素加入，为了让栈中的元素可以完全弹出，这得结合题目来看，不清楚的看后面题目。
for (遍历这个数组)
if (栈空 || 栈顶元素大于等于当前比较元素)
入栈;
else
while (栈不为空 && 栈顶元素小于当前元素)
栈顶元素出栈;
更新结果;
当前数据入栈;
应用：
1.
最基础的应用就是给定一组数，针对每个数，寻找它和它右边第一个比它大的数之间有多少个数。
题目：
链接.
题意：
有一群牛站成一排，每头牛都是面朝右的，每头牛可以看到他右边身高比他小的牛。给出每头牛的身高，要求每头牛能看到的牛的总数。
思路：
这就是求每个数和它右边第一个比它大的数之间的数的个数，分别求出后相加即可。朴素的做法是双重循环遍历，时间复杂度为O(n^2)，用单调栈为O(n)。
代码：
#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<list>
#define endl '\\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 8e4+10,M=20;
const int inf=0x3f3f3f3f;
int n,m,t,x;
int main()
int i,n,top,a[N]; //top指向栈顶元素
ll ans; //存储最终结果
stack<int> st; //st为栈，每次入栈的是每头牛的位置
while(~scanf("%d",&n))
while(!st.empty()) st.pop(); //清空栈
for(i=0;i<n;i++)
scanf("%d",&a[i]);
a[n]=inf; //将最后一个元素设为最大值
ans=0;
for(i=0;i<=n;i++)
if(st.empty()||a[i]<a[st.top()])
//如果栈为空或入栈元素小于栈顶元素，则入栈
st.push(i);
else
while(!st.empty()&&a[i]>=a[st.top()])
//如果栈不为空并且栈顶元素不大于入栈元素，则将栈顶元素出栈
top=st.top(); //获取栈顶元素
st.pop(); //栈顶元素出栈
//这时候也就找到了第一个比栈顶元素大的元素
//计算这之间牛的个数，为下标之差-1
ans+=(i-top-1);
st.push(i); //当所有破坏栈的单调性的元素都出栈后，将当前元素入栈
cout << ans << endl;
return 0;
2.
给定一序列，寻找某一子序列，使得子序列中的最小值乘以子序列的长度最大。
题目：
链接.
题意：
题解：
这里引用一下《算法进阶指南》里面的讲解，觉得讲的真心不错。
代码：
#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<list>
#define endl '\\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 1e5+10,M=20;
const int inf=0x3f3f3f3f;
ll n,m,t,x;
ll arr[N];
int main()
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
while(cin>>n)
if(n==0)
break;
stack<ll> st;
arr[n + 1] = -1;
for (int i = 1; i <= n;i++)
cin >> arr[i];
ll ans = 0;
for (int i = 1; i <= n + 1; i++)
if (st.empty() || arr[st.top()] <= arr[i])
st.push(i);
else
while (!st.empty()&&arr[st.top()] > arr[i])
t=st.top();
st.pop();
ll temp = (i - t) * arr[t];
if(temp>ans)
ans = temp;
st.push(t);
arr[t] = arr[i];
cout << ans<< endl;
// system("pause");
return 0;
3.
给定一序列，寻找某一子序列，使得子序列中的最小值乘以子序列所有元素和最大。
题目：
链接.
题意：
求序列中的最小值乘以这个序列的和的值最大，是典型的单调栈的应用。一般的思路是求每个数字所在的能使其值为区间最小值的最大区间，然后求出区间元素和乘以该值并更新结果的最大值。普通的做法时间复杂度为O(n^2)，用单调栈可以达到O(n)。
题解：
用一个单调递减栈，如果栈为空或入栈元素大于等于栈顶元素，则入栈，否则将破坏栈的单调性，则将栈顶元素出栈，直到栈为空或碰到第一个小于等于入栈元素的元素。然后将最后一次出栈的栈顶元素入栈，并将其向左右拓展，并更新其对应的值。最后一次出栈的栈顶元素就是当前入栈元素可以向左拓展到的最大距离。
代码：
#include<iostream>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<list>
#define endl '\\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 1e5+10,M=20;
const int inf=0x3f3f3f3f;
int n,m,t,x;
int main()
int i,n,pos1,pos2; //pos1和pos2记录区间的开始和结束位置
//tmp为临时变量，记录区间内的和；top指向栈顶元素；ans为结果；sum为前缀和
ll tmp,top,ans,a[100010],sum[100010];
stack<int> st; //单调栈，记录元素位置
while(~scanf("%d",&n))
while(!st.empty()) st.pop(); //清空栈
sum[0]=0;
for(i=1;i<=n;i++)
scanf("%lld",&a[i]);
sum[i]=sum[i-1]+a[i]; //计算前缀和
a[n+1]=-1; //将最后一个设为最小值，以最后让栈内元素全部出栈
ans=0;
for(i=1;i<=n+1;i++)
if(st.empty()||a[i]>=a[st.top()])
//如果栈为空或入栈元素大于等于栈顶元素，则入栈
st.push(i);
else
while(!st.empty()&&a[i]<a[st.top()])
//如果栈非空并且入栈元素小于栈顶元素，则将栈顶元素出栈
top=st.top();
st.pop();
tmp=sum[i-1]-sum[top-1]; //计算区间内元素和
tmp*=a[top]; //计算结果
if(tmp>=ans)
//更新最大值并记录位置
ans=tmp;
pos1=top;
pos2=i;
st.push(top); //将最后一次出栈的栈顶元素入栈
a[top]=a[i]; //将其向左向右延伸并更新对应的值
printf("%lld\\n",ans);
printf("%d %d\\n",pos1,pos2-1);
return 0;
线性表--单调栈(代码片段)
目录前言一、单调栈简介1.1单调递增栈1.2单调递减栈二、单调栈适用场景2.1寻找左侧第一个比当前元素大的元素2.2寻找左侧第一个比当前元素小的元素2.3 寻找右侧第一个比当前元素大的元素2.4 寻找右侧第一个比当前元素小的... 查看详情
单调栈(代码片段)
1、分类单调递增栈：数据出栈的序列为单调递增序列单调第减栈：数据出栈的序列为单调递减序列 2、操作（以单调递增栈为例）如果新元素比栈顶元素大， 入栈如果新元素比栈顶元素小，栈顶元素出栈，直到栈顶元素... 查看详情
单调栈(代码片段)
单调递增栈：栈顶到栈底为递增，数据出栈的序列为单调递增序列单调递减栈：栈顶到栈底为递减，数据出栈的序列为单调递减序列栈内可存储下标，也可存储元素(code:)for(inti=1;i<=n;++i)while(top&&a[i]>a[st[top]])top--;st[++top]=... 查看详情
单调栈与单调队列(代码片段)
单调栈特点栈内的元素单调递增或者单调递减，可以在\(O(n)\)的时间内求出数列中所有数的左边或右边第一个比其大或小的元素，总时间复杂度为\(O(n)\)例子单调栈中一般存索引一个单调递增栈s=[0,10,20,t]代表栈中a[1]~a[9]的元素大... 查看详情
单调栈(代码片段)
单调栈唠嗑：寒假遇到过，当时没能弄懂，昨天在算法进阶指南看到，再一次理解之后感觉对它的认识更近了一步，写一写记录一下，也理一下思路。分类：单调递增栈：单调递增栈就是从栈底到... 查看详情
单调栈(代码片段)
单调栈简单点说就是维护一个元素满足单调性的栈，即栈内元素总是单调的 找出序列中某一个元素左边/右边 第一个 比它大/小的元素的位置用单调栈做的话，复杂度是O（n）的 如果要求比某一元素小的第一个元... 查看详情
单调栈（poj2559）(代码片段)
DescriptionAhistogramisapolygoncomposedofasequenceofrectanglesalignedatacommonbaseline.Therectangleshaveequalwidthsbutmayhavedifferentheights.Forexample,thefigureontheleftshowsthehistogramthatconsists 查看详情
最小栈（单调栈）(代码片段)
设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。push(x)——将元素x推入栈中。pop() ——删除栈顶的元素。top() ——获取栈顶元素。getMin()——检索栈中的最小元素。 示... 查看详情
[数据结构]单调栈(代码片段)
[数据结构]单调栈单调栈为栈中元素按照升序排列(递增栈)或降序排列(递减栈)的栈，通常可以用来寻找下一个最大/最小的题。以[1,3,4,2]数组实现一个递增栈：到[1,3,4]这里其实都没有什么问题，一直是处在递增的状态... 查看详情
[数据结构]单调栈(代码片段)
[数据结构]单调栈单调栈为栈中元素按照升序排列(递增栈)或降序排列(递减栈)的栈，通常可以用来寻找下一个最大/最小的题。以[1,3,4,2]数组实现一个递增栈：到[1,3,4]这里其实都没有什么问题，一直是处在递增的状态... 查看详情
用数组模拟栈队列以及单调栈单调队列应用(代码片段)
用数组模拟栈//tt表示栈顶intstk[N],tt=0;//向栈顶插入一个数stk[++tt]=x;//从栈顶弹出一个数tt--;//栈顶的值stk[tt];//判断栈是否为空if(tt>0)用数组模拟队列//hh表示队头，tt表示队尾intq[N],hh=0,tt=-1;//向队尾插入一个数q[++tt]=x;//从队头弹出... 查看详情
golang代码实现单调栈(代码片段)
有种特殊的栈，叫做单调栈，顾名思义就是栈底到栈顶呈现单调特性，比如对于列表：[]int6,10,3,7,4,12，如果要实现单调栈，并不是所有入栈后呈降序或升序排列就是单调栈，如单调递增栈：6|栈空，入栈|[6]10|10>6,符合递增，入... 查看详情
[算法]单调栈专题(代码片段)
单调栈是一种理解起来很容易，但是运用起来并不那么简单的数据结构。一句话解释单调栈，就是一个栈，里面的元素的大小按照他们所在栈内的位置，满足一定的单调性。题目是这样的，给一个数组，返回一个大小相同的数组... 查看详情
84.largestrectangleinhistogram.单调栈(代码片段)
Givennnon-negativeintegersrepresentingthehistogram‘sbarheightwherethewidthofeachbaris1,findtheareaoflargestrectangleinthehistogram.Aboveisahistogramwherewidthofeachbaris1,givenheight=[2,1,5,6,2,3].The 查看详情
单调栈的应用(代码片段)
单调栈，顾名思义，就是存放的元素是单调的栈。单调栈主要是用来计算某个数左边/右边第一个比它小/大的数，基本上所有单调栈的题都是用到单调栈的这个功能。下面以计算某个数左边第一个比它小的数为例，... 查看详情
单调栈的应用(代码片段)
单调栈，顾名思义，就是存放的元素是单调的栈。单调栈主要是用来计算某个数左边/右边第一个比它小/大的数，基本上所有单调栈的题都是用到单调栈的这个功能。下面以计算某个数左边第一个比它小的数为例，... 查看详情
单调栈(代码片段)
单调栈是一种栈的特殊的用法。 单调栈中包括单调增栈，单调减栈。 以下说明单调栈的两种基本的用法： 1.单调增栈用来求解vector中每个元素前一个比其小的元素，并且时间复杂度是O(n). 2.单调减栈用来求解... 查看详情
单调栈(代码片段)
...元素top()–得到栈顶元素getMin()–得到栈中最小元素单调栈)O(1)https://www.acwing.com/solution/AcWing/content/749/我们除了维护基本的栈结构之外，还需要维护一个单调栈，来实现返回最小值的操作。下面介绍如何维护单调栈：当我们... 查看详情