邻接子数组。有比O(n^2)更好的解吗？

Question

我正在解决以下问题：

null

输入：Array arr是一个非空的唯一整数列表，范围在1到1,000,000,000之间，大小N在1到1,000,000之间

输出：一个数组，其中每个索引i包含一个整数，表示ARR[i]的最大相邻子数组数

示例:arr=[3,4,1,6,2]输出=[1,3,1,5,1]

  int[] countSubarrays(int[] arr) {
  int len = arr.length;
  int[] output = new int[arr.length];
  
  for (int i = 0; i < len; i++) { 
    output[i] = 1;
    
    // move right
    for (int j = i + 1; j < len; j++) {
      if (arr[i] <= arr[j]) {
        break;
      }
      output[i]++;
    }
    
    // move left
    for (int j = i - 1; j >= 0; j--) {
      if (arr[i] <= arr[j]) {
        break;
      }
      output[i]++;
    }
  }
  
  return output;
}

计算从1到N的每个i的g[i]是一种很有希望的方法，但我们仍然需要考虑如何尽可能有效地这样做。我们可以观察到，纯粹基于G[i-1]、A[i-1]和A[i]的值来计算G[i]是不可能的；我们可能还需要更多关于早期a值的信息，但希望避免简单地扫描所有这些值。从以前的指数j（如j k的G[i]的候选者？如果我们能在遍历数组时保持关于这些可能的候选索引集的信息，就有可能有效地确定每个i实际上等于g[i]的那个。

我无法直觉地理解这背后的逻辑。有什么建议吗？

Answer 1

因此，首先，让我们通过只考虑以其最大值结束的子数组来简化问题。（可以使用相同的方法找到以最大值开始的子数组，但从数组的末尾开始并向后工作，而不是从开头开始并向前工作。幸运的是，我们真的不需要担心重复计数以相等值开始和结束的子数组，因为问题指定所有元素都是不同的，所以唯一这样的子数组是长度为1的子数组，我们只需从最终答案中减去n就可以轻松处理。）

我从您的代码中看到，您已经发现，对于任何给定的索引I，我们需要找到的是最大的索引j ；< I，a[j] > a[I]，因为子数组[(j+1)..I]，[(j+2)..I]，...[I..I]正是满足我们条件的子数组。在您的代码中，当您向后工作到j时，您将增加output；但是实际上可以在循环结束后编写输出+=i-j。这意味着，只要我们能在摊销常数时间内找到j，我们就能在O(n)时间内解决问题，而不是在O(n²)时间内解决问题。

那么，我们该怎么做呢？诀窍是在一个名为G的数组中跟踪我们以前的答案；例如，如果A是[10,0,5,3]，那么G将是[-1,0,0,2]。（你知道为什么吗？）然后，当我们试图找到G[i]时，我们可以参考我们已经存储在G[0...(i-1)]中的值，以便更快地向后跳；我们可以编写j=g[j]而不是j--。

对于每一个单独的指数i，仍有可能需要多达n次向后跳跃才能找到G[i]；但只有当a[i]大于所有以前的值，并且所有以前的值都在减小时，才会发生这种情况。那只能发生一次。更一般地，跨越i的所有值的总跳跃次数将是O(n)，因为我们只有在第一次找到大于a[j]的值时才从j跳到g[j]。（你知道为什么吗？）