朱文康


私信TA

用户名:dotcpp0739013

访问量:155

签 名:

等  级
排  名 2648
经  验 2209
参赛次数 35
文章发表 1
年  龄 0
在职情况 学生
学  校 怀化学院
专  业

  自我简介:

TA的其他文章

测试数据有问题
浏览:127

错误样例样例:
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分

2 人评分

  评论区

  • «
  • »