怎么优化成一次单调栈寻找的,我看题解都是这样
  • 板块P1901 发射站
  • 楼主thehanged
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/5/8 09:40
  • 上次更新2024/5/8 16:47:01
查看原帖
怎么优化成一次单调栈寻找的,我看题解都是这样
638272
thehanged楼主2024/5/8 09:40

求指教

我是用单调栈找了两次,为啥他们可以优化成一次。

没有懂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;
}
2024/5/8 09:40
加载中...