arrays - 范围小于 k 的子数组数

Question

给定一个(未排序的)数组 S 和某个整数 k，找出满足 S[i...j] < k 的对 i,j 的数量。其中范围是 max(S[i...j]) - min(S[i...j])。

我在面试中收到了这个问题，在对 S 进行排序后只能得出一个 O(nlogn) 的解决方案。但是，我被告知有一个 O(n) 的解决方案。有什么想法吗？

Answer 1

从 i,j = 0 开始，我们可以迭代 j，跟踪最小值和最大值。当通过提高 max 范围变为 >= k 时，我们需要找到一个新的 i，其中 min(s[i..j]) > max - k(另一种情况的模拟)。

显然我们可以通过从 j 向后搜索找到这个索引，但我们需要从 i 向前搜索以保持运行时间线性(例如:1 2 3 4 5 6 且 k = 4 将回溯多个元素并在每个元素中向后搜索步骤，而前向搜索确保每个 i 只被考虑一次)。

为了能够做到这一点，我们可以保留两个具有单调升序/降序数组值的索引列表。

因此，当我们在“外部”循环中迭代 j 时，我们从升序列表中删除所有值大于 s[j] 的索引，然后追加 j。降序列表的模拟。由于我们总是追加一个元素，并且删除的次数不能超过添加的次数，所以这部分应该仍然是线性的。

当在“内部”循环中搜索一个值足够接近新最小值/最大值的新 i 时，我们从列表的前面删除访问过的元素。

编辑:代码

import java.util.LinkedList;

public class Ranges {

  public static int countRanges(int[] s, int k) {
    int i = 0;
    int min = s[0];
    int max = s[0];
    LinkedList<Integer> ascending = new LinkedList();
    ascending.add(0);
    LinkedList<Integer> descending = new LinkedList();
    descending.add(0);
    System.out.println("[0...0]");
    int count = 1;
    for (int j = 1; j < s.length; j++) {
      int value = s[j];

      while (!ascending.isEmpty() && s[ascending.getLast()] > value) {
        ascending.removeLast();
      }
      ascending.add(j);

      while (!descending.isEmpty() && s[descending.getLast()] < value) {
        descending.removeLast();
      }
      descending.add(j);

      if (s[j] > max) {
        max = s[j];
        if (max - min >= k) {
          while(max - s[ascending.getFirst()] >= k) {
            ascending.removeFirst();
          }
          i = ascending.getFirst();
          min = s[i];
          while (descending.getFirst() < i) {
            descending.removeFirst();
          }
        }
      } else if (s[j] < min) {
        min = s[j];
        if (max - min >= k) {
          while(s[descending.getFirst()] - min >= k) {
            descending.removeFirst();
          }
          i = descending.getFirst();
          max = s[i];
          while (ascending.getFirst() < i) {
            ascending.removeFirst();
          }
        }
      }
      System.out.println("[" + i + "..." + j + "]");
      count += j - i + 1;  // New subarrays involving j
    }
    return count;
  }


  public static void main(String[] args) {
    final int[] s = new int[] {1, 7, 2, 3, 4, 1, 2, 5, 6};
    final int k = 3;
    System.out.println("count: " + countRanges(s, k));
  }
}

工作笔记:https://i.imgur.com/G2FlSoc.jpg噢:)