arrays - 左/右旋转数组后最长递增子数组的长度

Question

我在一个有竞争力的编程平台上遇到过这个问题:

给定一个长度为 N 和 Q 的查询数组，其中查询是数组的左旋转或右旋转。每次旋转后求数组中最长子数组的长度。

虽然 O(N * Q) 方法是一个可以接受的答案，但我不禁认为必须有一个更快的方法，因为每次旋转只会修改 2 个潜在子的长度序列。

我考虑过复制数组并追加复制的数组以获得长度为 2N 的数组:

那么如果我取一个大小为 N 的窗口:

• 对于 0 次旋转，答案将是 [0, N - 1] 范围内窗口开始的最长递增子数组。
• 向左旋转 1 次，答案将是 [1, N] 范围内最长的子数组，即将窗口向右移动 1 个单位。
• 向左旋转 k 次，答案将在范围 [k, N - 1 + k] 内，这将使窗口从初始位置向右移动 k 个单位。

我计划通过将窗口向右移动 1 个单位来保存所有可能查询的答案，直到我检查了 N-1 次左旋转。

寻找范围 [0, N - 1] 的最长子数组将是 O(N)，但我无法减少每次窗口转换后花费的时间。

我曾想过使用优先级队列，我会在其中存储窗口中的每个索引以及以所述索引为起始的可能的最长子数组的长度，并使用子数组的长度作为优先级。我在轮类后更新队列时遇到问题。我最初认为我不必进行太多更新将算法的复杂性降低到 O(N logN) 但这里我没有更新在窗口移动之前添加的子数组。

我觉得如果优先级队列管理得当，预处理的复杂度可以降低到O(N logN)，每个查询的复杂度可以降低到O(1)。

编辑:问题实际上是关于最长递增子数组，但我使用子序列而不是使用编辑后已更正的词子数组。

Answer 1

考虑重复序列(如您建议的那样)。尝试对元素进行分组，如果 ai <= ai+1，则 ai 应该与 ai+1 在同一组中。通过这种方式，您可以将序列划分为递增的连续子序列。将这些子序列成对存储(开始、结束)。您可以在 O(N) 中获得它们的排序列表。

现在让我们计算所有循环移位的结果。让我们从前 N 个元素开始。创建一个将按长度对子序列进行排序的 BST。插入所有在 N 之前结束的子序列。如果存在任何在 N 之前开始并在 N 之后结束的子序列(或之后在我们的窗口之前开始并在内部结束的任何子序列)，我们将称其为特殊的。要获得结果，只需取 BST 中子序列的最大长度和位于所考虑窗口内的特殊子序列的一部分。当你移动到下一个类次时，特殊的可能完全适合，所以只需将它插入 BST。您可能还需要从 BST 中删除一个在窗口之前开始的子序列(然后它变成特殊的)。因此，您可以从 O(log n) 的 BST 中的所有子序列和 O(1) 的特殊子序列中获得最大长度(同时最多有两个)。

您甚至可以通过将 BST 更改为队列来获得 O(n) 的复杂度(有时称为最小/最大队列，或滑动窗口最大/最小值，或其他任何东西，它可以获取元素的最小值/最大值, 添加新的和删除第一个添加的全部在 O(1)) 中