算法学习之单调栈

发射站

题目描述

某地有 $N$ 个能量发射站排成一行，每个发射站 $i$ 都有不相同的高度 $H_i$，并能向两边（两端的发射站只能向一边）同时发射能量值为 $V_i$ 的能量，发出的能量只被两边最近的且比它高的发射站接收。显然，每个发射站发来的能量有可能被 $0$ 或 $1$ 或 $2$ 个其他发射站所接受。

请计算出接收最多能量的发射站接收的能量是多少。

输入格式

第 $1$ 行一个整数 $N$。

第 $2$ 到 $N+1$ 行，第 $i+1$ 行有两个整数 $H_i$ 和 $V_i$，表示第 $i$ 个发射站的高度和发射的能量值。

输出格式

输出仅一行，表示接收最多能量的发射站接收到的能量值。答案不超过 32 位带符号整数的表示范围。

样例 #1

样例输入 #1

3
4 2 
3 5 
6 10

样例输出 #1

7

提示

对于 $40\%$ 的数据，$1\le N\le 5000,1\le H_i\le 10^5,1\le V_i\le 10^4$。

对于 $70\%$ 的数据，$1\le N\le 10^5,1\le H_i\le 2\times 10^9,1\le V_i\le 10^4$。

对于 $100\%$ 的数据，$1\le N\le 10^6,1\le H_i\le 2\times 10^9,1\le V_i\le 10^4$。

我们正常的思路就是直接模拟

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e+6 + 5;
int n;
ll h[N];
int v[N];
int ans[N];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> h[i] >> v[i];
	}
	h[0] = h[n+1] = 2000000000;
	for (int i = 1;i<=n; i++) {
		for (int j = i - 1; j > 0; j--) {
			if (h[j] > h[i]) {
				ans[j] += v[i];
				break;
			}
		}
		for (int j = i + 1; j <= n; j++) {
			if (h[j] > h[i]) {
				ans[j] += v[i];
				break;
			}
		}
	}
	int pp = 0;
	for (int i = 1; i <= n; i++) {
		pp = max(ans[i], pp);
	}
	cout << pp;
	return 0;
}

超时了两个点

我们需要维护一个单调栈

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e+6 + 5;
int n;
ll h[N];
int v[N];
int ans[N];
int q[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[q[top]] < h[i]) // 出栈操作，这个必须保证里面有东西，且栈顶的是最小的, 如果进来的大于栈顶的，那么这个就要出栈
		{
			ans[i] += v[q[top--]];
		}
		// 进栈操作
		q[++top] = i;
		ans[q[top - 1]] += v[i];       // 给最近一个高的加上去
	}
	int pp = 0;
	for (int i = 1; i <= n; i++) {
		pp = max(pp, ans[i]);
	}
	cout << pp;
	return 0;
}