发射站
题目 发射站
思路分析
是每根柱子发送的信号只能被最近的比它高的接收到
而不是 每根柱子只能接收到最近的比它矮的
也就是说 一根较高的柱子可能接收多个信号
比如上图的高度为6的柱子 可以接收高度为4的柱子的2和高度为3柱子的5 一共得7
也就是说 在单调栈里面 不止是栈头是答案
而是单调栈里面所有小于当前柱子的都要累加起来
这个过程可以并在出栈里面 出栈时就res[i]+=
当然 还得累加一遍右边的
所以就是左右都做一遍单调栈 然后出现往上趋势出栈，同时累加答案
最后对答案数组求一个最大值即可
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int h[N],v[N],ans[N];
int stk[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>h[i]>>v[i];
}
int top=0;
for(int i=1;i<=n;i++){
//找左边比它矮的数 所以出现往上趋势就出栈
while(top && h[stk[top]]<h[i]){
ans[i]+=v[stk[top]];
top--;
}
stk[++top]=i;
}
top=0;
for(int i=n;i>=1;i--){
while(top && h[stk[top]]<h[i]){
ans[i]+=v[stk[top]];
top--;
}
stk[++top]=i;
}
int res=0;
for(int i=1;i<=n;i++){
res=max(res,ans[i]);
}
cout<<res<<endl;
return 0;
}
💬 评论