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

问题描述

给出一个（未排序的）数组S和一些整数k，找到对i，j的数量，使得S [i ... j]的范围k。范围是max（S [i ... j]）-min（S [i ... j]）。

我在一次采访中收到了这个问题，在对S进行排序后只能提供O（nlogn）解决方案。但是，我被告知存在O（n）解决方案。有想法吗？

解决方案

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

很显然，我们可以通过从j向后搜索来找到该索引，但是我们需要从i向前搜索以保持运行时线性（例如：1 2 3 4 5 6 with k = 4将在每个步骤中通过向后搜索来回溯几个元素，而向前搜索可确保每个i仅被考虑一次）。

要做到这一点，我们可以保留两个具有单调递增或递减数组值的索引列表。

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

在搜索具有值的新i时（足够接近内部循环中的新的最小值/最大值），我们从列表的开头删除访问的元素。

编辑：代码

  import java.util.LinkedList; 
 
公共类范围{
 
 public static int countRanges（int [] s，int k）{
 int i = 0; 
 int min = s [0]; 
 int max = s [0]; 
 LinkedList< Integer>升序= new LinkedList（）; 
 ascending.add（0）; 
 LinkedList< Integer>下降=新的LinkedList（）; 
ending.add（0）; 
 System.out.println（ [0 ... 0]）; 
 int计数= 1; 
 for（int j = 1; j< s.length; j ++）{
 int value = s [j]; 
 
而（！ascending.isEmpty（）& s [ascending.getLast（）]> value）{
 ascending.removeLast（）; 
} 
 ascending.add（j）; 
 
而（！descending.isEmpty（）& s [descending.getLast（）]< value）{
ending.removeLast（）; 
} 
ending.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]; 
而（descending.getFirst（）< i）{
ending.removeFirst（）; 
} 
} 
}否则，如果（s [j]< min）{
 min = s [j]; 
 if（max-min> = k）{
 while（s [descending.getFirst（）]-min> = k）{
ending.removeFirst（）; 
} 
 i = ending.getFirst（）; 
 max = s [i]; 
而（ascending.getFirst（）< i）{
 ascending.removeFirst（）; 
} 
} 
} 
 System.out.println（ [ + i + ... + j +]）; 
 count + = j-i + 1; //涉及j 
} 
返回计数的新子数组； 
} 
 
 
 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：）

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]).

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?

解决方案

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).

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.

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.

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.

Edit: Code

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));
  }
}

Working notes: https://i.imgur.com/G2FlSoc.jpg O:)

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