范围小于k的子阵列数

Question

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

我在一次采访中收到了这个问题，经过排序后只能得出一个O（nlogn）解。但是，有人告诉我有一个O（n）解。有什么想法吗？

Answer 1

不幸的是，公认的答案是错误的。有关详细说明，请参阅https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/discuss/?currentPage=1

上面的leetcode问题并不是这个SO问题所要问的，但是更改一行代码可以解决这个问题。

这是一个C代码（请参阅https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/discuss/609771/JavaC++Python-Deques-O（N）用于解释）

unsigned long countPairs(vector<int>& nums, int limit) { //Number of sub-arrays with range less than or equal to k
    limit--; //Number of sub-arrays with range less than k
    deque<int>minDeque,maxDeque;
    int start=0;
    unsigned long ans=0;
    for(int end =0;end<nums.size();++end){
        int w = nums[end];
        while(!minDeque.empty() && nums[minDeque.back()]>w) minDeque.pop_back();
        minDeque.push_back(end);

        while(!maxDeque.empty() && nums[maxDeque.back()]<w) maxDeque.pop_back();
        maxDeque.push_back(end);

        if(!maxDeque.empty() and !minDeque.empty()) {
            while (nums[maxDeque.front()] - nums[minDeque.front()] > limit) {
                if (!maxDeque.empty() and nums[maxDeque.front()] == nums[start]) maxDeque.pop_front();
                if (!minDeque.empty() and nums[minDeque.front()] == nums[start]) minDeque.pop_front();
                start++;
            }
            ans += end - start + 1;
        }
    }
    return ans;
}

Answer 2

您可以使用经典2指针技术的变体来实现这一点。不同之处在于，您需要跟踪值在k范围内的范围的起始索引，以及该范围内的最小值和最大值，以便我们知道当前值何时超出范围（起始索引处的值不一定是最小值或最大值）。另一个需要注意的是，当当前值超出范围时，新的开始索引不一定由最小值或最大值指示，而是必须从当前索引开始向后迭代进行搜索。

正如KSwama所指出的，有可能必须多次向后迭代相同的元素，因此时间复杂度不会是线性的。我认为最坏的情况意味着对大多数元素迭代多达k次，因此复杂度可能类似于O（n×k）。

将开始索引设置为0，将min和max设置为S[0]。然后，遍历输入，对于每个值S[i]，如果需要，将min或max调整为S[i]。当您遇到一个值S[i]大于或等于min k时，将min和max设置为S[i]，然后从i向后迭代（同时调整min），直到您找到一个小于或等于max-k的值S[j]；j 1然后成为新的开始索引。对于每个值S[i]，它添加到总数中的对数是i-start。

例子：

S = [1,3,-1,2,5,3,6,2,4,0]  
k = 5

我们从以下内容开始：

i  S[p] start min  max pairs

0    1    0    1    1    -  
1    3    0    1    3    1  
2   -1    0   -1    3    2  
3    2    0   -1    3    3  
4    5  

此时，我们得到了一个大于min k的值。因此，我们将当前值S[i]设置为新的min和max，并向后迭代（同时更新min），直到找到小于或等于max-k的第一个值，即S[2]=-1；因此，S[3]成为新的最小值，3成为新的开始索引：

i  S[p] start min  max pairs

4    5    3    2    5    1  
5    3    3    2    5    2  
6    6    3    2    6    3  
7    2    3    2    6    4  
8    4    3    2    6    5  
9    0  

此时我们得到一个小于或等于max-k的值。所以我们将min和max设置为0，并向后迭代（同时更新max），直到我们达到S[6]，它大于或等于min k，所以7成为新的开始索引；请注意，新的max不是S[start]，而是我们在途中传递的更高值4。

i  S[p] start min  max pairs

9    0    7    0    4    2  

总的成对数是23（如果我理解了它们的正确计数方式的话）。

如果你想把复杂性降低到O（n），有很多选择，但是Stefan Haustein的答案可能是可行的。

Answer 3

从i开始，j=0，我们可以迭代j，跟踪最小值和最大值

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

为了能够做到这一点，我们可以保留两个索引列表，其中包含单调递增/递减的数组值。

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

当在“内部”循环中搜索一个新的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.jpgO：）