求指教
我是用单调栈找了两次,为啥他们可以优化成一次。
没有懂wuwuu
代码实现如下:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;
int h[N], v[N], res[N], sta[N], top;
int main(){
ios::sync_with_stdio(false);
int n;
cin >> n;
for(int i = 1; i <= n; ++ i) cin >> h[i] >> v[i];
for(int i = 1; i <= n; ++ i){
while(top > 0 && h[sta[top]] < h[i]) -- top;
if(top > 0) res[sta[top]] += v[i];
sta[++ top] = i;
}
memset(sta, 0, sizeof sta), top = 0;
for(int i = n; i >= 1; -- i){
while(top > 0 && h[sta[top]] < h[i]) -- top;
if(top > 0) res[sta[top]] += v[i];
sta[++ top] = i;
}
cout << *max_element(res + 1, res + n + 1) << endl;
return 0;
}