我要招人

去企业版

首页 > 试题广场 >

我们惺惺相惜

[编程题]我们惺惺相惜

热度指数：697 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 1024M，其他语言2048M
算法知识视频讲解

给定一个长度为 $n$ 的数组 $a$ ，我们定义一个区间 $[l,r]$ 是好的，当且仅当这个区间可以分成两个非空的子序列，元素之间相对顺序不变，使得这两个子序列都是严格单调递增子序列。

对于给出多次询问，你需要问答区间是不是好区间。

输入描述:

第一行一个整数 ，表示有  次询问。

对于每次询问，第一行两个整数 ，第二行  个整数 ，表示数组 。

接下来  行，每行两个整数 ，表示询问的区间。

单个测试文件保证  和  的和均不超过 。

输出描述:

对于每次询问，输出一行，如果区间是好区间，输出 ，否则输出 。

示例1

输入

输出

YES
YES
YES
NO
YES

算法知识视频讲解

Java

pe1shen9

要使一个区间 [l,r] 可以分成两个严格递增的子序列，这意味着原区间中的元素不能有“三个递减”的点。换句话说，如果存在三个索引 i,j,k（l≤i<j<k≤r）满足 ai≥aj≥ak，那么无论如何分割，这三个元素中至少有两个会在同一个子序列中，导致该子序列不是严格递增的。因此，这样的区间不可能是“好的”。

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for (int i = 0; i < t; i++) {
int n = in.nextInt();
int q = in.nextInt();
int[] arr = new int[n];
for (int j = 0; j < n; j++) {
arr[j] = in.nextInt();

}

//left[j] 表示 j 左边第一个 ≥ a[j] 的元素的索引

int[] left = new int[n];
Arrays.fill(left, -1);
Deque<Integer> stack = new ArrayDeque<>();
for (int j = 0; j < n; j++) {
while (!stack.isEmpty() && arr[stack.peek()] < arr[j]) {
stack.pop();
}
if (!stack.isEmpty()) {
left[j] = stack.peek();
}
stack.push(j);
}

stack.clear();

//right[j] 表示 j 右边第一个 ≤ a[j] 的元素的索引

int[] right = new int[n];
Arrays.fill(right, -1);
for (int j = n - 1; j >= 0; j--) {
while (!stack.isEmpty() && arr[stack.peek()] > arr[j]) {
stack.pop();
}
if (!stack.isEmpty()) {
right[j] = stack.peek();
}
stack.push(j);

}

//如果 left[j] 和 right[j] 都存在，则记录 (left[j], right[j])

List<int[]> list = new ArrayList<>();
for (int j = 0; j < n; j++) {
if (left[j] != -1 && right[j] != -1) {
list.add(new int[] {left[j], right[j]});
}

}

//按照left[j]的大小进行排序

//由于题目最大时间为4MS，直接遍历是否符合好区间即可

//如果时间复杂度要求更高，可以用二分优化

list.sort((o1, o2) -> o1[0] - o2[0]);
for (int j = 0; j < q; j++) {
int l = in.nextInt() - 1;
int r = in.nextInt() - 1;
boolean falg = true;
for (int k = 0; k < list.size(); k++) {
if (list.get(k)[0] >= l && list.get(k)[1] <= r) {
falg = false;
break;
}
}
System.out.println(falg ? "YES" : "NO");
}
}
}
}

发表于 2025-06-09 20:20:12 回复(1)

提交观点

问题信息

数组美团单调栈

难度：

1条回答 42收藏 524浏览

我们惺惺相惜

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题