笔试练习1分享（弱鸡版）
区间删除
有一个长度为 𝑛的数组 𝑎，要使得数组 𝑎 有序（单调不降）。 选择一段区间 [𝑙,𝑟],(1≤𝑙≤𝑟≤𝑛)[l,r],(1≤l≤r≤n)，将数组的这一段删除，其他的部分（如果存在的话）就按顺序拼在一起。
现在想知道有多少种不同的选择区间的方案。
注：空数组也满足有序，即你可以选择 [1,𝑛][1,n] 这个区间。
个人第一版代码（超时）总体时间复杂度：O(n³)：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = in.nextInt();
}
int count = 0;
// 枚举所有可能的删除区间 [l, r]
for (int l = 1; l <= n; l++) {
for (int r = l; r <= n; r++) {
// 构建删除 [l, r] 后的新数组
int[] b = new int[n - (r - l + 1)];
int idx = 0;
for (int i = 0; i < n; i++) {
if (i + 1 >= l && i + 1 <= r) continue;
b[idx++] = a[i];
}
// 判断新数组是否单调不降
boolean ok = true;
for (int i = 0; i < b.length - 1; i++) {
if (b[i] > b[i + 1]) {
ok = false;
break;
}
}
if (ok) count++;
}
}
System.out.println(count);
}
}
枚举区间：O(n²)
每次构造数组并判断有序：O(n)
总体时间复杂度：O(n³)
AI提示办法：解决每次构造需要判断有序。如何优化判断？把判断拿出去，枚举 [𝑙,𝑟]区间O(n²)，在外部进行1-l和r-n的有序判断，只要让l与r两端满足升序即可。
import java.util.Scanner;
public class Main {
static int res=0;
static int n=0;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n=in.nextInt();
int[] arr=new int[n];
for(int i=0;i<n;i++){
arr[i]=in.nextInt();
}
int start=0;
while(start<n-1&&arr[start]<arr[start+1]){
start++;
}
int end=n-1;
while(end>0&&arr[end]<arr[end-1]){
end++;
}
for (int l = 0; l <= start; l++) {
for (int r = end; r <= n; r++) {//r=Math.max(start+1.end)保证覆盖到start到end之间的非有序
if (l == 0 || r == n || arr[l - 1] <= arr[r]) {
res++;
}
}
}
System.out.println(res);
}
}
依旧超时解决（纯AI，本彩笔改破防了，比较搞笑的是某通AI给的代码只是对最小r找的判断条件和计数修改了一下，把题目喂给它也是过不了的代码，我的代码卡住了AI让AI过不了，男泵）：
问题分析
我们需要计算有多少种不同的区间删除方案，使得删除后的数组剩余部分是非递减的。具体来说，我们需要找到所有满足以下条件的区间 [l,r]（1≤l≤r≤n）：
删除区间 [l,r] 后，剩余部分的数组是非递减的。
关键观察
非递减条件：剩余部分必须满足 a[1]≤a[2]≤⋯≤a[l−1]≤a[r+1]≤⋯≤a[n]。 预处理：
预处理两个数组 p 和 s：
p[i]：从 a[1] 到 a[i] 的最长连续非递减前缀长度。
s[i]：从 a[i] 到 a[n] 的最长连续非递减后缀长度。
合法区间的条件：
对于区间 [l,r]，必须满足：
a[l−1]≤a[r+1]（如果 l>1 且 r<n）。
p[l−1]=l−1（即 a[1..l−1] 是非递减的）。
s[r+1]=n−r（即 a[r+1..n] 是非递减的）。
解决步骤
预处理 p 和 s 数组：
p[i]：如果 a[i]≥a[i−1]，则 p[i]=p[i−1]+1；否则 p[i]=1。
s[i]：如果 a[i]≤a[i+1]，则 s[i]=s[i+1]+1；否则 s[i]=1。
枚举左端点 l：
如果 p[l−1]=l−1，说明 a[1..l−1] 不是非递减的，跳过。
否则，二分查找最小的 r 使得 a[l−1]≤a[r+1] 且 s[r+1]=n−r。
统计方案数： 对于每个合法的 l，所有 r≥找到的最小 r 都是合法的，因此方案数为 n−r+1。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] a = new int[n + 2]; // 1-based indexing
for (int i = 1; i <= n; i++) {
a[i] = scanner.nextInt();
}
a[0] = Integer.MIN_VALUE;
a[n + 1] = Integer.MAX_VALUE;
int[] p = new int[n + 2]; // p[i]: length of longest non-decreasing prefix ending at i
int[] s = new int[n + 2]; // s[i]: length of longest non-decreasing suffix starting at i
p[1] = 1;
for (int i = 2; i <= n; i++) {
if (a[i] >= a[i - 1]) {
p[i] = p[i - 1] + 1;
} else {
p[i] = 1;
}
}
s[n] = 1;
for (int i = n - 1; i >= 1; i--) {
if (a[i] <= a[i + 1]) {
s[i] = s[i + 1] + 1;
} else {
s[i] = 1;
}
}
long ans = 0;
for (int l = 1; l <= n; l++) {
if (p[l - 1] != l - 1) {
continue; // a[1..l-1] is not non-decreasing
}
int low = l, high = n;
int best = n + 1; // smallest r such that a[l-1] <= a[r+1] and s[r+1] = n - r
while (low <= high) {
int mid = (low + high) / 2;
if (a[l - 1] <= a[mid + 1] && s[mid + 1] == (n - mid)) {
best = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
ans += (n - best + 1);
}
System.out.println(ans);
}
}
复杂度分析
时间复杂度：O(nlogn)，预处理 p 和 s 数组是 O(n)，枚举左端点 l 并二分查找 r 是 O(nlogn)。
空间复杂度：O(n)，用于存储 p 和 s 数组。
#刷题##区间删除#
投递上海得物信息集团有限公司等公司10个岗位 >
查看11道真题和解析