题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
import java.util.*;
import java.io.*;
import static java.lang.Math.*;
/**
* @author zzk
* @version 1.0
* @since 2024/3/29
*/
public class Main {
static Scanner sc = new Scanner(System.in);
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int n, N = (int) 1e5 + 10;
static int[] h = new int[N], left = new int[N], right = new int[N];
public static void main(String[] args) throws Exception {
while((n = sc.nextInt()) != 0) {
for(int i = 1; i <= n; ++ i) {
h[i] = sc.nextInt();
}
long ans = 0;
h[0] = -1;
h[n + 1] = -1;
Arrays.fill(left, 0);
Arrays.fill(right, 0);
Stack<Integer> stack = new Stack<>();
stack.push(0);
for(int i = 1; i <= n; ++ i) {
while(h[stack.peek()] >= h[i]) {
stack.pop();
}
left[i] = i - stack.peek();
stack.push(i);
}
stack.clear();
stack.push(n + 1);
for(int i = n; i >= 1; -- i) {
while(h[stack.peek()] >= h[i]) {
stack.pop();
}
right[i] = stack.peek() - i - 1;
stack.push(i);
}
for(int i = 1; i <= n; ++ i) {
ans = max(ans, (long) h[i] * (left[i] + right[i]));
}
System.out.println(ans);
}
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla