范围小于 k 的子数组的数量 [英] Number of subarrays with range less than k

问题描述

给定一个(未排序的)数组 S 和某个整数 k，求 i,j 对的数量，使得 S[i...j] 的范围

ķ.其中范围是 max(S[i...j]) - min(S[i...j]).

Given an (unsorted) array S and some integer k, find the number of pairs i,j such that the range of S[i...j] < k. Where range is max(S[i...j]) - min(S[i...j]).

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

I received this question in an interview and was only able to come up with a O(nlogn) solution after sorting S. However, I was told there is an O(n) solution. Any ideas?

推荐答案

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

Starting with i,j = 0, we could iterate j, keeping track of min and max. When the range becomes >= k via raising max, we need to find a new i where min(s[i..j]) > max - k (analog for the other case).

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

Obviously we could find this index by searching backwards from j, but we need to search forward from i to keep the runtime linear (example: 1 2 3 4 5 6 with k = 4 would backtrack several elements with backwards search in each step, while forward search makes sure each i is only considered once).

为此，我们可以保留两个具有单调递增/递减数组值的索引列表.

To be able to do so, we could keep two lists of indices with monotonously ascending / descending array values.

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

So as we iterate j in the "outer" loop, we remove all indices with values bigger than s[j] from the ascending list and then append j. Analog for the descending list. Since we always append one element and the number of removals can't exceed the number of additions, this part should still be linear.

在内部"循环中搜索具有足够接近新最小值/最大值的值的新 i 时，我们从列表的前面删除访问过的元素.

While searching a new i with a value that is sufficiently close to the new min/max in the "inner" loop, we remove the visited elements from the front of the lists.

编辑:代码

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 O:)

这篇关于范围小于 k 的子数组的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！