最大区间
作者:
不知名的fE
,
2025-02-04 19:45:45
,
所有人可见
,
阅读 2
import java.util.Scanner;
import java.util.Stack;
public class Main {
static final int N = 3000100;
static int[] a = new int[N], l = new int[N], r = new int[N];
static int n;
public static void main(String[] args) {
/*
对于每一个确定的a[i],枚举他们的最大宽度取max
*/
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
a[0] = a[n + 1] = -1;//两个哨兵
for (int i = 1; i <= n; i++) {
a[i] = sc.nextInt();
}
// 单调栈
//先找到左边第一个比他小的数
Stack<Integer> stk = new Stack<>();
stk.push(0);
for (int i = 1; i <= n; i++) {
while (!stk.isEmpty() && a[stk.peek()] >= a[i]) stk.pop();
l[i] = stk.peek();
stk.push(i);
}
stk.clear();
//再找到右边第一个比他小的数
stk.push(n + 1);
for (int i = n; i >= 1; i--) {
while (!stk.isEmpty() && a[stk.peek()] >= a[i]) stk.pop();
r[i] = stk.peek();
stk.push(i);
}
long ans = 0;
for (int i = 1; i <= n; i++) {
//len : r[i] - l[i] - 1 => r[i]的位置已经比a[i]小不能取到
//因此是r[i] - l[i] + 1 - 2
ans = Math.max(ans, (long) a[i] * (r[i] - l[i] - 1));
}
System.out.println(ans);
}
}