错误样例样例:
3

3 1 0

预期:2
实际:3
注意事项:
Snipaste_2024-05-30_16-16-03.png
Snipaste_2024-05-30_16-16-23.png


参考代码:

贴上代码: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.0分

2 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 0 条评论

暂无评论