错误样例样例:
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++代码)浏览:932 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码) 用函数传参的方法浏览:4120 |
震宇大神的杀毒软件 (C语言代码)浏览:1348 |
哥德巴赫曾猜测 (C语言代码)浏览:1147 |
C二级辅导-阶乘数列 (C语言代码)浏览:736 |
WU-整数平均值 (C++代码)浏览:1307 |
【金明的预算方案】 (C++代码)浏览:996 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:943 |
A+B for Input-Output Practice (III) (C语言代码)浏览:594 |
钟神赛车 (C语言代码)浏览:665 |