滑动窗口中的最小值

Question

滑动窗口中的最小值

6

有没有特定的算法可以让我在小/中型滑动窗口（典型大小为600，所有元素均为整数）上保持最小值/最大值？窗口实际上是流中的最后N个观测值。因此，我在每个时间单位添加一个新的观测值并删除最旧的观测值，所以我想保留最后N个观察值的最小值和最大值。

这是与Sliding window minimum algorithm中所述问题不同的问题，因为我没有维护整个数据，因此“基于索引”的解决方案在这里不适用。此外，我的输入数据本身将处于循环数组中。

堆可能不太适合：我不会删除/弹出最小/最大元素，而是最旧的元素，这将使拥有堆的目的失效。

基于log(n)复杂度的结构，例如红黑树将完美地工作，而伸展树可能更适合我所拥有的数据类型，但对于我要处理的规模来说，它们是否有点过度设计？

- KS1

2

迟做总比不做好，可能会对未来有所帮助。确实存在一个算法：http://home.tiac.net/~cri/2001/slidingmin.html - Wam

1

上面的链接无法使用，但我在archive.org上找到了一个版本：http://web.archive.org/web/20120805114719/http://home.tiac.net/~cri/2001/slidingmin.html - user674669

你实际上不需要跟踪一个不断增加的索引，你只需要对窗口大小取模来跟踪它。因此，在你的情况下，索引将从0到599，然后返回到0。 - Christoffer Hammarström

这个回答解决了你的问题吗？https://dev59.com/9Woy5IYBdhLWcg3wg-Um - templatetypedef

2个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Varun Verma · Answer 1

解决在输入数据流中查找最大值的问题的方案托管在下面的链接上，您可以轻松地将其调整为查找最小值。

输入流的大小并不重要，可以是无限的。该算法的执行时间复杂度为摊销常数O(1)。

https://github.com/varoonverma/code-challenge.git

- mukesh prajapati · Answer 2

这是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;
  }


}