範圍小於k的子陣列的數量

Question

給定一個（未排序的）數組S和一些整數k，找出對i，j的數量，使得S [i ... j]的範圍爲k [0128]k。範圍是max（S [i ... j]） - min（S [i ... j]）。

我在一次採訪中收到了這個問題，在排序後只能提出一個O（nlogn）解決方案。但是，我被告知有一個O（n）解決方案。有任何想法嗎？

Answer 1

從i開始，j = 0，我們可以迭代j，跟蹤最小值和最大值。當範圍通過提高max變爲> = k時，我們需要找到一個新的i，其中min（s [i..j]）> max - k（另一種情況的模擬）。

很顯然，我們可以通過從j向後搜索來找到該索引，但是我們需要從i向前搜索以保持運行時間線性（例如：k = 4時的例子：1 2 3 4 5 6會向後搜索幾個元素每一步，而向前搜索確保每個我只被考慮一次）。

爲了做到這一點，我們可以通過單調遞增/遞減數組值來保存兩個索引列表。因此，當我們在「外部」循環中迭代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Ø:)

Answer 2

您可以使用經典的雙指針技術的變體來做到這一點。不同之處在於，您需要跟蹤其值在k範圍內的範圍的起始索引，以及該範圍內的最小值和最大值的跟蹤，以便我們知道當前值何時超出範圍（在起始索引不一定是最小值或最大值）。另外要注意的是，當前值超出範圍時，新的起始索引不一定由最小值或最大值指示，而必須從當前索引開始向後迭代搜索。正如KSwama所指出的那樣，可能需要多次向後迭代相同的元素，因此時間複雜度將不是線性的。我認爲最壞的情況將意味着對大多數元素進行k次迭代，所以複雜度可能類似於O（n × k）。

將開始索引設置爲0，並將最小值和最大值設置爲S [0]。然後，迭代輸入和每個值S [i]，必要時將最小值或最大值調整爲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 

在這一點上，我們來到比分鐘+ k大的值。因此，我們將當前值S [i]設置爲新的最小值和最大值，並向後迭代（同時更新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成爲新的開始索引;請注意新的最大值不是S [開始]，而是我們在路上傳遞的較高值4。

i S[p] start min max pairs 

9 0 7 0 4 2 

而對的總數是23（如果我已經理解了它們被正確計數的方式）。

---

如果你想打倒複雜度爲O（n），也有多種選擇，但斯特凡Haustein的答案很可能是要走的路。