原题目链接

问题描述

给定一个长度为 n 的序列 A_i，求一对 L, R 使得：

(R - L + 1) * min(A_L, A_{L+1}, ..., A_R)

的值尽可能大，其中 min 表示该区间中的最小值。

你只需要输出该表达式的最大值，无需输出具体的 L 和 R。

---

输入格式

• 第一行包含一个整数 n，表示序列的长度。
• 第二行包含 n 个整数，分别表示 A_1, A_2, ..., A_n，相邻两个整数之间使用一个空格分隔。

---

输出格式

输出一行，包含一个整数，表示答案。

---

样例输入

5
1 1 3 3 1

---

样例输出

6

---

评测用例规模与约定

• 对于 40% 的评测用例：1 ≤ n ≤ 5000，1 ≤ A_i ≤ 5000
• 对于所有评测用例：1 ≤ n ≤ 3×10^5，1 ≤ A_i ≤ 10^9

c++代码

#include<bits/stdc++.h>
#include<stdio.h>using namespace std;typedef long long ll;ll n, ans = 0;
vector<ll> arr, nextsmall, lastsmall;int main() {stack<ll> st, sk;scanf("%lld", &n);arr = vector<ll>(n), nextsmall = vector<ll>(n, n), lastsmall = vector<ll>(n, -1);for (ll i = 0; i < n; i++) {scanf("%d", &arr[i]);}for (ll i = 0; i < n; i++) {while(!st.empty() && arr[i] < arr[st.top()]) {nextsmall[st.top()] = i;st.pop();}st.push(i);}for (ll i = n - 1; i >= 0; i--) {while(!sk.empty() && arr[i] < arr[sk.top()]) {lastsmall[sk.top()] = i;sk.pop();}sk.push(i);}for (ll i = 0; i < n; i++) {ll left = lastsmall[i] + 1, right = nextsmall[i] - 1;ans = max(ans, (right - left + 1) * arr[i]);}printf("%lld", ans);return 0;
}//by wqs

算法讲解

用单调栈

这道题目，先选取一个值假设这个值就是最小的，然后不断向两边扩散，使得R - L最大，前提是保证这个值最小。

如何快速得到L和R，就是快速得到右边第一个比他大的，和左边第一个比他小的，这就是经典的单调栈问题。