第一题，合并球
题解：一开始写了一次暴力双循环，直接O(n^2)严重超时，后面于是又想到了O(n)时间复杂度的链表，但是还是卡在 最后一个数据会TLE，我也是高兴的拍起来安塞腰鼓和华氏护肤水，后面学长给我说用单调栈，我才想起来，只需要维护右边的一个端口，因此单调栈就可以解决这个问题，于是乎，我又写了一篇单调栈的写法，也是很成功的就过了
那么我们来说明一下单调栈的做法，首先，我们通过看题可以发现，这题每次都是在序列的右端进行操作，那么我们就可以想到一个数据结构，栈，因为栈也是在一端进行操作，那么我们用一个单调栈，每次添加元素的时候判断一下，如果添加的元素和站顶的元素相同，那么就将添加的元素+1，然后将现在的栈顶的元素排除，然后继续比较添加的元素和栈顶元素
#include<bits/stdc++.h>
using namespace std;
int n;
int a[200005];
stack<int>q;//创建一个栈
int flag;
int cnt;
int main()
{
cin>>n;
cnt=n;
a[0]=-1;
for(int i=1;i<=n;i++)
{
cin>>a[i];//输入每一个元素
}
for(int i=1;i<=n;i++)
{
while(!q.empty()&&q.top()==a[i])//如果栈不为空，且栈顶元素和要添加的元素相同的话
{
q.pop();
a[i]++;//要添加的元素+1，然后继续和新的栈顶元素比较
}
q.push(a[i]);
}
printf("%d\n",q.size());//判断栈里面还有几个元素，也就是题目所求
return 0;
}第二题，奶牛排队
题解：这题虽然乍一看好像和单调栈没有任何的关系，但是要是仔细思考过后，会发现，其实这也是单调栈的一类习题，我们首先来简单阐述一下题意，就是说我们有一群奶牛去排队，我们在这个队列中截取一部分，最左边的A奶牛是这一部分最矮的奶牛，而最右边的B奶牛是这一部分最高的奶牛，要求出这种部分的最长的长度是多少？
ok，那么题意阐述完以后，我们现在来说一下思路，我们说了这道题要用单调栈去做，那么哪里体现的单调栈呢？
我们需要循环枚举B奶牛 ，既然我们已经枚举了最右端的B奶牛，那么我们就要确保它在这一段序列中一定是最高的那个，因此我们就要先去寻找左边第一个比B奶牛高的，A奶牛一定在左边第一个奶牛比B奶牛高的右边
但是想要找到A奶牛，就要不断去寻找右边第一个比（左边第一个比B奶牛高的奶牛）低的奶牛（我服了，真绕口啊，还好这题自己搞出来了）
因此，这题的思路就变成了构造一个栈，一开始充当单调递增栈，循环跑一遍，先去求出左边第一个比第i个奶牛高的奶牛的位置，然后将栈pop空，然后再充当单调递减栈，循环跑一遍，找到右边第一个比第i个奶牛低的奶牛的位置，最后for循环跑一遍，寻找最长的队列即可（当然了，但一开始那个右数组，需要将值都赋值为n+1）
#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
int h;
int flag;
}a[100005];
int l[100005];
int r[100005];
stack<node>q;
int maxn=0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].h;
a[i].flag=i;
}
//求出左边第一个比第i个元素大的
for(int i=1;i<=n;i++)
{
while(!q.empty()&&q.top().h<a[i].h)
{
q.pop();
}
if(!q.empty())
{
l[i]=q.top().flag;
}
else
{
l[i]=0;
}
q.push(a[i]);
}
//将栈排空，这个是这细节，第一次就错在这里了
while(!q.empty())
{
q.pop();
}
for(int i=1;i<=n;i++)
r[i]=n+1;
//求出右边第一个比第i个元素小的
for(int i=1;i<=n;i++)
{
while(!q.empty()&&q.top().h>a[i].h)
{
r[q.top().flag]=i;
q.pop();
}
q.push(a[i]);
}
for(int i=n;i>=1;i--)
{
for(int j=l[i]+1;j<i;j++)
{
if(r[j]>i)
{
maxn=max(maxn,i-j+1);
break;
}
}
if(i<=maxn)
break;
}
printf("%d\n",maxn);
return 0;
}第三题，音乐会的等待
这题的做题历程只能用艰辛来说，一开始想错了，导致我求的结果和答案完全不符，就过了一个可怜的数据点，当我想尽办法终于想出来的时候，最后三个点又全都TLE了，后来去看了一发题解，才知道，后续增加了三个超大数据，因此还需要用一个结构体存储相同的元素有多少个
做题思路：
一开始，我想的就是一个十分简单的单调栈问题，for循环去遍历每个位置的元素，用单调栈，去找出右边第一个大于这个元素的元素，这样就算一个，并且如果等于的话也算一个，但是不用弹出
只要栈中有元素就可以sum++，去找出有多少对
因而，我们首先，可以用单调递增栈，只要弹出一个元素，统计数量就可以++，但是加入栈顶元素==要比较的元素，那么就先弹出，然后用cnt统计数量，最后一起加入到栈里面，最后手机sum的大小就是所求，但是最后的超大数据是过不了的
那么我们首先来看我一开始的错误代码
错误代码，不能过最后的三个超大数据，但是可以迅速理解这题的做题思路
#include<bits/stdc++.h>
using namespace std;
long long n;
struct node{
long long h;
long long flag;
}a[500005];
stack<node>q;
long long sum;
long long cnt;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].h;
a[i].flag=i;
}
//搞一个单调递增栈,找出每一个右边第一个大于i的
for(int i=1;i<=n;i++)
{
cnt=1;
while(!q.empty()&&q.top().h<=a[i].h)
{
if(q.top().h==a[i].h)
{
cnt++;
}
sum++;
q.pop();
}
if(!q.empty())
sum++;
while(cnt--)
q.push(a[i]);
}
printf("%lld\n",sum);
return 0;
}AC代码，成功将最后的几个超大数据给过了，这边也是感谢前辈的智慧
正确代码的思路：用pair存储两个键值，第一个键值为数值的大小，第二个键值为重复数的数量，节约时间的地方就在于在统计总共对数的时候，直接加的是重复数的大小，这样就不用一个一个弹出来，再一个一个加回去，因此可以压缩时间成本，减小时间复杂度
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define integer
pair<int,int> p;//第一个键值存储的是数值的大小，第二个键值存储的是这个数有多少个相同的
int ans;
int n;
int h[500005];
stack< pair<int,int> >q;
integer main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>h[i];
}
for(int i=1;i<=n;i++)
{
p=make_pair(h[i],1);
while(!q.empty()&&h[i]>=q.top().first)
{
if(q.top().first==h[i])
{
p.second+=q.top().second;
}
ans+=q.top().second;
q.pop();
}
if(!q.empty())
ans++;
q.push(p);
}
printf("%lld\n",ans);
}
