错误样例样例:
3
3 1 0
预期:2
实际:3
注意事项:

参考代码:
贴上代码:right方法是错误的
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
/**
* https://www.dotcpp.com/oj/problem3248.html
* 暴力:枚举以每个队员为左端点,再枚举右端点。找到左端点右侧最近的比它大的数。 这题如果先暴力分析一下,就容易想到单调栈。可惜暴力分析时老想着树状数组去了。
*/
public class Main {
static int n;
static int maxn = (int) (1e5 + 10);
static int[] arr = new int[maxn];
static int[] left = new int[maxn];
static int[] right = new int[maxn];
static int[] stack = new int[maxn];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for (int i = 1; i <= n; i++) {
arr[i] = sc.nextInt();
}
//正确代码
// int ans=Math.min(left(arr), right(arr));
// System.out.println(ans);
// //下面是错误代码,但是可以过oj
System.out.println(right(arr));
}
//对数器,松开即用
// static{int cnt=(int)1e5;for(int i=1;i<=cnt;i++){compare(5);}}
public static void compare(int maxn) {
Random r = new Random();
n = r.nextInt(maxn) + 1;
arr = new int[n + 1];
for (int i = 1; i <= n; i++) {
arr[i] = r.nextInt(maxn);
}
int l = left(arr);
int right = right(arr);
int ans=Math.min(l, right);
if (ans != right) {
System.out.println(Arrays.toString(arr));
System.out.println("error,ans=" + ans + ";\tright=" + right);
System.out.println(1 / 0);
}
}
public static int left(int[] arr) {
int t = 0;
for (int i = 1; i 0 && arr[stack[t - 1]] < arr[i]) {
right[stack[t - 1]] = i;
t--;
}
left[i] = t == 0 ? 1 : stack[t - 1];
stack[t++] = i;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = Math.max(ans, i - left[i] + 1);
}
return ans;
}
public static int right(int[] arr) {
int t = 0;
for (int i = 1; i 0 && arr[stack[t - 1]] <= arr[i]) {
right[stack[t - 1]] = i;
t--;
}
left[i] = t == 0 ? 1 : stack[t - 1];
stack[t++] = i;
}
while (t != 0) {
right[stack[--t]] = n;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = Math.max(ans, right[i] - i + 1);
}
return ans;
}
} 0.0分
2 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复