求最小数 * 区间和最大值

2020-12-06 21:44:22 我在这儿

``````import java.util.Deque;
import java.util.Scanner;

/**
* 〈一句话功能简述〉<br>
* 〈区间最大值：https://www.nowcoder.com/questionTerminal/3f4867e9cbe54403ac5df55b8e678df9〉
*
* @create 2020/12/5
* @since 1.0.0
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Deque<Integer> stack = new LinkedList<>(); // 单调递增栈（记录下标）
int n = in.nextInt();
int[] num = new int[n+1];
int[] prefix = new int[n+1];
Node[] goal = new Node[n+1];
for(int i = 1; i <= n; i++) {
goal[i] = new Node(); // 对象初始化必须 new
}
for(int i = 1; i <= n; i++) {
num[i] = in.nextInt();
prefix[i] = prefix[i-1] + num[i];
// 注意：因为最终的结果是对相应乘积求和而非取最大值，这里的出栈比较和下面的比较两处只能取一处等号
// eg: [1 2 2 2 1]
while(!stack.isEmpty() && num[stack.peek()] >= num[i]) stack.pop();
goal[i].start = stack.isEmpty() ? 0 : stack.peek(); // 栈空应该赋予 0 而非 i-1
stack.push(i);
}
stack.clear();
for(int i = n; i >= 1; i--) {
while(!stack.isEmpty() && num[stack.peek()] > num[i]) stack.pop();
goal[i].end = stack.isEmpty() ? n : stack.peek()-1; // 栈空时赋予 n 而非 i
stack.push(i);
}
long ans = 0;
for(int i = 1; i <= n; i++) ans = Math.max(ans, (long)(prefix[goal[i].end]- prefix[goal[i].start])*(long)num[i]);
System.out.print(ans);
}
}

class Node {
int start;
int end;
Node() {}
}
``````

https://www.cnblogs.com/emptyCoder/p/14094454.html