错误样例样例:
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、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复