子数组中元素范围小于k的数量

Question

给定一个未排序的数组S和一个整数k，找出所有满足区间S[i...j]的范围（即max(S[i...j]) - min(S[i...j])）小于k的(i,j)配对数量。

我在面试中遇到了这个问题，只能想到在对S进行排序后得到O(nlogn)时间复杂度的解法。但是我被告知有一个O(n)的解法。你们有什么想法吗？

- KSwama

---

这种形式的问题通常有一个动态规划的解决方案：https://en.wikipedia.org/wiki/Dynamic_programming - Lou Franco

是的，我尝试过使用DP，但是还没有想出一个合适的递推关系。 - KSwama

这是一个有趣的面试问题。我希望他们更关心你解决问题的方法，而不是你是否当场想出了答案。 - StriplingWarrior

Answer 1

您可以使用经典的双指针技术的变体来完成此操作。不同之处在于，您需要跟踪值在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），直到找到一个值S [j]，它小于或等于max-k; 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]设置为新的最小值和最大值，并向后迭代（同时更新最小值），直到找到第一个小于或等于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），直到达到大于或等于min+k的S[6]，因此7成为新的起始索引；请注意，新的最大值不是S[start]，而是我们在路上传递的更高值4。

i  S[p] start min  max pairs

9    0    7    0    4    2  

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

---

如果你想把复杂度降低到O(n)，有很多选择，但Stefan Haustein的答案可能是最好的选择。

- m69 ''snarky and unwelcoming''

---

我觉得这个算法可能不是O(n)，因为在最坏的情况下，你可能被迫在每一步都回溯。但我不确定，因为我们有一个滑动窗口，我感觉一个索引需要重新检查的次数可能是有限的。 - KSwama

@KSwama 实际上，你可能是对的。我明天会再看一下它。 - m69 ''snarky and unwelcoming''

Answer 2

从 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。降序列表类似。由于我们总是添加一个元素，而删除的数量不能超过添加的数量，因此此部分仍应是线性的。

在“内部”循环中搜索具有足够接近新 min/max 值的新 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 O:)

（注：本段内容为原文，无需翻译）

- Stefan Haustein

---

经过仔细研究您的解决方案，我有点困惑。您所说的“从升序列表中删除所有较小或相等的值”是什么意思？具体而言，“较小或相等”是指比什么小或相等？ - KSwama

假设我们想从 1 2 3 1 5 6 中的倒数第二个数变为 2。在升序列表中，插入第二个 1 需要删除 2 和 3，因为如果我们向后遍历，需要遍历更小的值。所以实际上应该是“大于”。已相应地编辑了文本。 - Stefan Haustein

起初我认为你把事情复杂化了，但我忽略了反向迭代可能多次遍历相同元素的事实。 - m69 ''snarky and unwelcoming''

这是一个有趣的问题，但我不认为我会在面试中问到它... - Stefan Haustein

很不幸，代码有漏洞。我已经在 https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/ 提交了代码，其中50/61个测试用例已经通过。 - duplex143

Answer 3

很遗憾，被接受的答案有缺陷。详细解释请参见https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/discuss/?currentPage=1&orderBy=most_votes&query=。虽然上述 LeetCode 问题并不完全符合此 SO 问题的要求，但更改一行代码即可使其适用于此问题。以下是C++代码（请参见https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/discuss/609771/JavaC%2B%2BPython-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;
}

- duplex143