是否有特定的算法允许我在中小型滑动窗口（典型大小为 600，所有元素均为整数）上保持最小/最大值？窗口实际上是流中的最后 N 个观测值。所以，我添加了一个新的观察并删除了每个时间单位最旧的观察，所以我想保留最后 N 个观察的最小值和最大值。
这是与滑动窗口最小算法中所述的问题不同的问题，因为我不维护整个数据，因此“基于索引”的解决方案在这里不适用。此外，我的输入数据本身将位于一个循环数组中。
堆可能不会很好地工作：我不会删除/弹出最小/最大元素，而是最旧的元素，这将破坏首先拥有堆的目的。
log(n) 基于复杂性的结构（例如红黑树）可以正常工作，而展开树可能更适合我所拥有的数据类型，但是对于我的大小来说它们是否有点矫枉过正？ d 处理？
找到最大输入数据流的问题的解决方案托管在以下链接上，您也可以轻松调整它以找到 Min。
输入流的大小并不重要，可以是无限的。该算法以摊销常数 O(1) 复杂度执行。
这是java中的代码
import java.io.*;
import java.util.*;
public class MinInwindow {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
int k = sc.nextInt();
printMinInWindow(arr, n, k);
}
static void printMinInWindow(int[] arr, int n, int k) {
int start = 0, last = 0;
ArrayList<Integer> list = new ArrayList<Integer>(k);
while (last < n) {
int val = arr[last];
if (last < k) {
list = addNewINtoList(list, val);
last++;
} else {
//print minimum from window
System.out.print(list.get(0) + " ");
int startValue = arr[start];
start++;
list = removefromListIfAvailable(list, startValue);
list = addNewINtoList(list, val);
last++;
}
}
System.out.println(list.get(0) + " ");
}
static ArrayList<Integer> addNewINtoList(ArrayList<Integer> list, int val) {
if (list.isEmpty()) {
list.add(val);
} else {
int size = list.size();
while (size > 0 && list.get(size - 1) > val) {
list.remove(size - 1);
size--;
}
list.add(val);
}
return list;
}
static ArrayList<Integer> removefromListIfAvailable(ArrayList<Integer> list, int val) {
if (list.isEmpty()) {
return list;
}
int startValue = list.get(0);
if (startValue == val) {
list.remove(0);
}
return list;
}
}