题解：P12241 [蓝桥杯 2023 国 C] 最大区间

题意简述

给定一个长度为

n

的序列，求最大的

(R - L + 1) \times \min(A_L, A_{L+1}, \ldots, A_R)

的值，就是区间长度乘以区间最小值的最大值。

算法思路

通过正向逆向两次单调栈扫描预处理，找出每个点作为区间最小点能获得的最大区间，很明显，区间越长越好。有一道极其相似的题：洛谷 P2422 良好的感觉。

确定左右边界：
- 先初始化，初始化左端点为 $0$ ，右端点为 $n+1$ 。
- 正向逆向跑一遍单调栈，求出每个点左边和右边第一个比 $A_i$ 小的点的位置。
- 此时 $A_i$ 作为最小值的最大区间为 $(l_i, r_i)$ ，实际正确的区间长度为 $r_i - l_i - 1$ ，因为是以 $A_i$ 为最小点的区间。
计算时注意：区间不包含左右端点。

复杂度分析

时间复杂度： $O(n)$ 正向逆向各一次扫描。

代码实现

CPP

#include<cstdio>
#include<stack>
#include<climits>
#include<algorithm>

using namespace std;

typedef long long ll;

const ll maxn = 3e5 + 5;

ll n, num[maxn];
void Input() {
	scanf("%lld", &n);
	for (ll i = 1; i <= n; ++i) {
		scanf("%lld", &num[i]);
	}
}


ll l[maxn], r[maxn];
void Init() {
	for (ll i = 1; i <= n; ++i) {
		l[i] = 0;
		r[i] = n + 1;
	}
}

stack<ll> s;
ll ans = INT_MIN;
void Sol() {
	for (ll i = 1; i <= n; ++i) {
		while (!s.empty() && num[s.top()] > num[i]) {
			r[s.top()] = i;
			s.pop();
		}
		s.push(i);
	}
	while (!s.empty()) {
		s.pop();
	}
	for (ll i = n; i >= 1; --i) {
		while (!s.empty() && num[s.top()] > num[i]) {
			l[s.top()] = i;
			s.pop();
		}
		s.push(i);
	}
	for (ll i = 1; i <= n; ++i) {
		ans = max(ans, ((r[i] - 1) - (l[i] + 1) + 1) * num[i]);
	}
}

int main() {
	Input();
	Init();
	Sol();
	printf("%lld", ans);
	return 0;
}

注意：初始化时左右边界分别为

0

和

n+1

。

题解：P12241 [蓝桥杯 2023 国 C] 最大区间

文章操作

题意简述

算法思路

复杂度分析

代码实现

相关推荐

评论

题解：P12241 [蓝桥杯 2023 国 C] 最大区间