旋转数组后最长递增子数组的长度left/right
Length of longest increasing subarray after rotating array left/right
我在一个有竞争力的编程平台上遇到这个问题：
给定一个长度为 N 和 Q 的查询数组，其中查询是数组的左旋转或右旋转。每次旋转后求数组中最长子数组的长度
尽管 O(N * Q) 方法是一个可以接受的答案，但我不禁认为必须有更快的方法，因为每次旋转都会修改长度只有 2 个潜在的子序列。
我考虑过复制数组并追加复制的数组以获得长度为 2N 的数组：
那么如果我拿 window 大小 N:
- 旋转 0 次，答案将是 [0，N - 1] 范围内最长的递增子数组，其中 window 将开始。
- 向左旋转 1 次，答案将是 [1, N] 范围内的最长子数组，即将 window 向右移动 1 个单位。
- 向左旋转 k 次，答案将在 [k, N - 1 + k] 范围内，这将从初始位置向右移动 window k 个单位。
我计划通过将 window 向右移动 1 个单位来保存所有可能查询的答案，直到我检查了 N-1 次左旋转。
查找范围 [0, N - 1] 的最长子数组将是 O(N)，但我无法减少每次 window 轮班后花费的时间。
我曾想过使用优先级队列，我会在其中存储 window 中的每个索引以及以所述索引为起始的可能的最长子数组的长度，并使用子数组的长度作为优先级.我在轮班后更新队列时遇到问题。我最初认为我不必进行太多更新将算法的复杂性降低到 O(N logN) 但在这里我没有更新在 window 被移动了。
我觉得如果优先级队列管理得当，预处理的复杂度可以降低到 O(N logN) 和 O(1) 每个查询。
编辑：问题实际上是关于最长递增子数组，但我使用了子序列而不是使用编辑后已更正的词子数组。
考虑重复序列（如您建议的那样）。尝试对元素进行分组，如果 ai <= ai+1，则 ai 应该与 ai+1 在同一组中。通过这种方式，您可以将序列划分为递增的连续子序列。将这些子序列成对存储（开始、结束）。您可以在 O(N) 中获得它们的排序列表。
现在让我们计算所有循环移位的结果。让我们从前 N 个元素开始。创建一个将按长度对子序列进行排序的 BST。插入所有在 N 之前结束的子序列。如果有任何子序列在 N 之前开始并在 N 之后结束（或之后的任何子序列在我们的 window 之前开始并在内部结束），我们将称其为特殊的。要获得结果，只需取 BST 中子序列的最大长度和位于所考虑 window 内的特殊子序列的一部分。当你移动到下一个班次时，特殊的可能完全适合，所以只需将它插入 BST。您可能还需要从 BST 中删除一个在 window 之前开始的子序列（然后它变成特殊的）。所以你可以从 O(log n) 中的 BST 中的所有子序列和 O(1) 中的特殊子序列中获得最大长度（同时最多有两个）。
您甚至可以通过将 BST 更改为队列（有时称为 min/max 队列，或滑动 window maximum/minimum 或其他任何方式来获得 O(n) 复杂度，它可以获取 minimum/maximum 个元素，添加新元素并删除第一个添加的元素，所有元素都在 O(1))
我在一个有竞争力的编程平台上遇到这个问题：
给定一个长度为 N 和 Q 的查询数组，其中查询是数组的左旋转或右旋转。每次旋转后求数组中最长子数组的长度
尽管 O(N * Q) 方法是一个可以接受的答案，但我不禁认为必须有更快的方法，因为每次旋转都会修改长度只有 2 个潜在的子序列。
我考虑过复制数组并追加复制的数组以获得长度为 2N 的数组：
那么如果我拿 window 大小 N:
- 旋转 0 次，答案将是 [0，N - 1] 范围内最长的递增子数组，其中 window 将开始。
- 向左旋转 1 次，答案将是 [1, N] 范围内的最长子数组，即将 window 向右移动 1 个单位。
- 向左旋转 k 次，答案将在 [k, N - 1 + k] 范围内，这将从初始位置向右移动 window k 个单位。
我计划通过将 window 向右移动 1 个单位来保存所有可能查询的答案，直到我检查了 N-1 次左旋转。
查找范围 [0, N - 1] 的最长子数组将是 O(N)，但我无法减少每次 window 轮班后花费的时间。
我曾想过使用优先级队列，我会在其中存储 window 中的每个索引以及以所述索引为起始的可能的最长子数组的长度，并使用子数组的长度作为优先级.我在轮班后更新队列时遇到问题。我最初认为我不必进行太多更新将算法的复杂性降低到 O(N logN) 但在这里我没有更新在 window 被移动了。
我觉得如果优先级队列管理得当，预处理的复杂度可以降低到 O(N logN) 和 O(1) 每个查询。
编辑：问题实际上是关于最长递增子数组，但我使用了子序列而不是使用编辑后已更正的词子数组。
考虑重复序列（如您建议的那样）。尝试对元素进行分组，如果 ai <= ai+1，则 ai 应该与 ai+1 在同一组中。通过这种方式，您可以将序列划分为递增的连续子序列。将这些子序列成对存储（开始、结束）。您可以在 O(N) 中获得它们的排序列表。
现在让我们计算所有循环移位的结果。让我们从前 N 个元素开始。创建一个将按长度对子序列进行排序的 BST。插入所有在 N 之前结束的子序列。如果有任何子序列在 N 之前开始并在 N 之后结束（或之后的任何子序列在我们的 window 之前开始并在内部结束），我们将称其为特殊的。要获得结果，只需取 BST 中子序列的最大长度和位于所考虑 window 内的特殊子序列的一部分。当你移动到下一个班次时，特殊的可能完全适合，所以只需将它插入 BST。您可能还需要从 BST 中删除一个在 window 之前开始的子序列（然后它变成特殊的）。所以你可以从 O(log n) 中的 BST 中的所有子序列和 O(1) 中的特殊子序列中获得最大长度（同时最多有两个）。
您甚至可以通过将 BST 更改为队列（有时称为 min/max 队列，或滑动 window maximum/minimum 或其他任何方式来获得 O(n) 复杂度，它可以获取 minimum/maximum 个元素，添加新元素并删除第一个添加的元素，所有元素都在 O(1))