单调栈-百亿富翁-最大区间

百亿富翁题目描述这天小明买彩票中了百亿奖金兴奋的他决定买下蓝桥公司旁的一排连续的楼房。已知这排楼房一共有 NN 栋编号分别为 1∼N1∼N第 ii 栋的高度为 hihi​。好奇的小明想知道对于每栋楼左边第一个比它高的楼房是哪个右边第一个比它高的楼房是哪个若不存在则输出 −1−1。但由于楼房数量太多小明无法用肉眼直接得到答案于是他花了 11 个亿来请你帮他解决问题你不会拒绝的对吧输入描述第 11 行输入一个整数 NN表示楼房的数量。第 22 行输入 NN 个整数相邻整数用空格隔开分别为 h1,h2,...,hNh1​,h2​,...,hN​表示楼房的高度。1≤N≤7×1051≤N≤7×1051≤hi≤1091≤hi​≤109。输出描述输出共两行。第一行输出 NN 个整数表示每栋楼左边第一栋比自己高的楼的编号。第二行输出 NN 个整数表示每栋楼右边第一栋比自己高的楼的编号。输入输出样例示例 1输入5 3 1 2 5 4输出-1 1 1 -1 4 4 3 4 -1 -1import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N7*100010; static int a[]new int[N]; static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i]Integer.parseInt(st.nextToken()); } //左边第一个比它高的楼房 int r1[]new int[n1]; StackInteger stack1new Stack();//维护一个单调递减的栈 for (int i 1; i n; i) { r1[i]-1; } for (int i 1; i n; i) { int ua[i]; while(!stack1.isEmpty() a[stack1.peek()]u)stack1.pop(); if(!stack1.isEmpty())r1[i]stack1.peek(); stack1.add(i); } for (int i 1; i n; i) { bw.write(r1[i] ); } bw.write(\n); //右边第一个比它高的楼房 int r2[]new int[n1]; StackInteger stack2new Stack();//维护一个单调递增的栈 for (int i n; i 0 ; i--) { r2[i]-1; } for (int i n; i 0 ; i--) { int ua[i]; while(!stack2.isEmpty() a[stack2.peek()]u)stack2.pop(); if(!stack2.isEmpty())r2[i]stack2.peek(); stack2.add(i); } for (int i 1; i n; i) { bw.write(r2[i] ); } br.close(); bw.flush(); bw.close(); } }最大区间问题描述给定一个长度为 nn 的序列 AiAi​求 L,RL,R 使 (R−L1)⋅min⁡(AL,AL1,…,AR)(R−L1)⋅min(AL​,AL1​,…,AR​) 尽可能大其中 min⁡min 表示最小值。你只需要输出最大的值即可不需要输出具体的 L,RL,R。输入格式输入的第一行包含一个整数 nn。第二行包含 nn 个整数分别表示 A1,A2,…,AnA1​,A2​,…,An​相邻两个整数之间使用一个空格分隔。输出格式输出一行包含一个整数表示答案。样例输入5 1 1 3 3 1样例输出6评测用例规模与约定对于 40%40% 的评测用例1≤n≤50001≤n≤50001≤Ai≤50001≤Ai​≤5000对于所有评测用例1≤n≤3×1051≤n≤3×1051≤Ai≤1091≤Ai​≤109。import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.*; public class Main { static int N3*100010; static int tree[]new int[4*N];//线段树 static int a[]new int[N]; static int n; static BufferedReader br new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args) throws IOException { StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); stnew StringTokenizer(br.readLine()); for (int i 1; i n; i) { a[i]Integer.parseInt(st.nextToken()); } //我们可以每一个a[i]为中心 向左找到第一个比他小的数 记为l //向右找到第一个比他小的数 记为r 所有满足a[i]是最小值的区间就是[l1,r-1] //长度为r-1-l-11r-l-1 //找左边第一个比它小的数 int r1[]new int[n1]; StackInteger stack1new Stack();//维护一个单调递增的栈 for (int i 1; i n; i) { r1[i]0; } for (int i 1; i n; i) { int ua[i]; while(!stack1.isEmpty() a[stack1.peek()]u)stack1.pop(); if(!stack1.isEmpty())r1[i]stack1.peek(); stack1.add(i); } //找右边第一个比它小的数 int r2[]new int[n1]; StackInteger stack2new Stack();//维护一个单调递增的栈 for (int i n; i 1 ; i--) { r2[i]n1; } for (int i n; i 1 ; i--) { int ua[i]; while(!stack2.isEmpty() a[stack2.peek()]u)stack2.pop(); if(!stack2.isEmpty())r2[i]stack2.peek(); stack2.add(i); } long resLong.MIN_VALUE; for (int i 1; i n; i) { int oa[i]; resMath.max(res, (long)o*(r2[i]-r1[i]-1));//这要用long } bw.write(res); br.close(); bw.flush(); bw.close(); } }