【JAVA】求数组连续区间内最大值与最小值的差不大于K的最大区间长度 Pro20210705
题目
给定数组，求在数组的连续区间内最大值与最小值的差不大于K的最大区间长度。
输入：
测试用例数量T
第1个测试用例数组长度N 差值K
第1个测试用例数组
第2个测试用例数组长度N 差值K
第2个测试用例数组
…
方法一：双指针+优先级队列
思路：
既然是连续区间，那么在下标left和下标right区间内，元素都是计算范围内的，所以用双指针指定连续区间即可；
最大值和最小值的获取，可以使用一个降序优先级队列和一个升序优先级队列；
步骤1：初始化 left = right = 0；且将Data[0]放入PQ1和PQ2；
步骤2：从两个PQ中获取极值min、max，若极值对应的下标，不在[left, right]范围内，则该极值已失效，扔掉重新获取；
步骤3：若max - min > K，则left++，然后重复步骤2和步骤3；若max - min <= K，则局部最优解ASW = right - left +1，然后right++，同时将Data[right]放入PQ1和PQ2，再重复步骤2和步骤3；
最终，当right右移至Data[N-1]，计算结束，ASW即为所求。
时间复杂度：NlogN（实际为NlogN）
空间复杂度：N（实际为2N）
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Pro_20210705_TwoPoint {
static class Node {
int idx, value;
public Node(int i, int v) {
this.idx = i;
this.value = v;
}
}
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("D:\\SW\\TestCase\\sample_input_20210705.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int T = Integer.parseInt(st.nextToken());
for (int test_case = 1; test_case <= T; test_case++) {
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[] arrs = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++)
arrs[i] = Integer.parseInt(st.nextToken());
PriorityQueue<Node> maxPQ = new PriorityQueue<>(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o2.value - o1.value;
}
});
PriorityQueue<Node> minPQ = new PriorityQueue<>(new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
return o1.value - o2.value;
}
});
int max, min, value = 0, left = 0, right = 0;
maxPQ.add(new Node(right, arrs[right]));
minPQ.add(new Node(right, arrs[right]));
while (right < N) {
while (maxPQ.peek().idx < left)
maxPQ.poll();
while (minPQ.peek().idx < left)
minPQ.poll();
max = maxPQ.peek().value;
min = minPQ.peek().value;
if (max - min > K) {
left++;
} else {
value = Math.max(value, right - left + 1);
if (right++ == N - 1)
break;
maxPQ.add(new Node(right, arrs[right]));
minPQ.add(new Node(right, arrs[right]));
}
}
System.out.println("#" + test_case + " " + value);
}
}
}
方法二：双指针+IndexTree
思路：
既然是连续区间，那么在下标left和下标right区间内，元素都是计算范围内的，所以用双指针指定连续区间即可；
最大值和最小值的获取，可以使用一个最大值IndexTree和一个最小值IndexTree；
步骤1：初始化 left = right = 0；并将Data[0]~Data[N-1]对应两个IndexTree的叶节点初始化好Tree；
步骤2：从两个Tree中获取极值min、max；
步骤3：若max - min > K，则left++，然后重复步骤2和步骤3；若max - min <= K，则局部最优解ASW = right - left +1，然后right++，再重复步骤2和步骤3；
最终，当right右移至Data[N-1]，计算结束，ASW即为所求。
时间复杂度：NlogN（实际为4NlogN）
空间复杂度：N（实际为4N~8N）
略
|