在滑动 window 中寻找第二大元素
Finding second largest element in sliding window
所以给定一个数组和一个 window 大小，我需要在每个 window 中找到第二大的。蛮力解决方案非常简单，但我想使用动态规划找到一个有效的解决方案
当我对大数组尝试暴力破解时超时，所以我需要找到更好的解决方案。我的解决方案是通过对它们进行排序并获取第二个元素来在每个滑动中找到第二大window，我知道某些数据结构可以更快地排序，但我想知道是否有更好的方法[=11] =]
有一个相对简单的动态编程O(n^2)解决方案：
为子集上的聚合值构建经典金字塔结构（您将下面两对的值组合起来以进行上面的每个步骤），在其中跟踪最大的 2 个值（及其位置），然后简单地保留最大的 2 个值4 个组合值中的一个（由于重叠而在实践中较少，使用位置来确保它们实际上不同）。然后，您只需从具有正确滑动 window 大小的图层中读取第二大值。
所以就拿一个像集合这样的数据结构，有序的存储数据。
就像如果你在集合上存储 4 2 6 它将存储为 2 4 6.
那么算法是什么：
让，
数组 = [12,8,10,11,4,5]
window尺寸=4
首先window=[12,8,10,11]
设置=[8,10,11,12]
如何获得第二高：
- 从集合中移除最后一个元素并存储在容器中。 set=[8,10,11],contaniner = 12
- 删除后，集合的当前最后一个元素是当前集合的第二大元素 window.
- 再次将容器中存放的移除元素放到set中，set=[8,10,11,12]
现在转移你的 window，
- 从集合中删除 12 并添加 4.
- 现在您将获得新的 window 并设置。
- 检查类似的过程。
在集合中删除和添加元素的复杂度约为 log(n)。
一招：
如果你总是想以降序存储数据，那么你可以将数据乘以-1来存储数据。当你弹出数据时，通过乘以-1来使用它。
我们可以使用双端队列来解决 O(n) 的问题。队列的前面将有更大的（和更早看到的）元素：
0 1 2 3 4 5
{12, 8,10,11, 4, 5}
window size: 3
i queue (stores indexes)
- -----
0 0
1 1,0
2 2,0 (pop 1, then insert 2)
output 10
remove 0 (remove indexes not in
the next window from the front of
the queue.)
3 3 (special case: there's only one
smaller element in queue, which we
need so keep 2 as a temporary variable.)
output 10
4 4,3
output 10
remove 2 from temporary storage
5 5,3 (pop 4, insert 5)
output 5
"pop" 和 "remove from front" 分别是 while A[queue_back] <= A[i] 和 while queue_front is outside next window（尽管队列中只剩下一个较小的元素表示复杂）。我们从队列的前面输出由第二个元素索引的数组元素（尽管我们的前面可能有一个特殊的临时朋友也曾经在前面；这个特殊的朋友一旦代表一个元素在外面就被丢弃window 或小于由前面第二个队列元素索引的元素）。双端队列的复杂度为 O(1)，可以从前端或后端移除。我们只插在后面。
根据 templatetypedef 在评论中的要求："how you determine which queue operations to use?" 在每次迭代中，使用索引 i，在将其插入队列之前，我们 (1) 从队列后面弹出每个元素表示数组中小于或等于 A[i] 的元素，并且 (2) 从队列的前面移除每个索引在当前 window 之外的元素。 （如果在（1）中，我们只剩下一个较小或相等的元素，我们将它保存为一个临时变量，因为它是当前第二大的。）
有很多方法可以解决这个问题。这里有几个选项。在下文中，我将让 n 表示输入数组中的元素数量，w 表示 window 大小。
选项 1：一个简单的 O(n log w) 时间算法
一个选择是维护一个平衡的二叉搜索树，其中包含当前 window 中的所有元素，包括重复元素。向这个 BST 中插入一些东西需要时间 O(log w)，因为 window 中总共只有 w 个元素，出于同样的原因，删除一个元素也需要时间 O(log w)。这意味着将 window 滑动一个位置需要时间 O(log w).
要在 window 中找到 second-largest 元素，您只需要应用 standard algorithm for finding the second-largest element in a BST，这在具有 w 个元素的 BST 中需要时间 O(log w) .
这种方法的优点是，在大多数编程语言中，编写这个代码会相当简单。它还利用了一堆 well-known 标准技术。缺点是运行时不是最优的，我们可以改进它。
选项 2：O(n) prefix/suffix 算法
这里有一个 linear-time 解决方案，实施起来相对简单。在高层次上，该解决方案的工作原理是将数组拆分为一系列块，每个块的大小为 w。例如，考虑以下数组：
31 41 59 26 53 58 97 93 23 84 62 64 33 83 27 95 02 88 41 97
假设 w = 5。我们将数组拆分为大小为 5 的块，如下所示：
31 41 59 26 53 | 58 97 93 23 84 | 62 64 33 83 27 | 95 02 88 41 97
现在，假设在这个数组的某处放置一个长度为 5 的 window，如下所示：
31 41 59 26 53 | 58 97 93 23 84 | 62 64 33 83 27 | 95 02 88 41 97
|-----------------|
请注意，此 window 将始终由一个块的后缀和后跟另一个块的前缀组成。这很好，因为它允许我们解决一个稍微简单的问题。想象一下，我们可以通过某种方式有效地确定任何块的任何前缀或后缀中的两个最大值。然后我们可以在任何 window 中找到 second-max 值，如下所示：
- 找出window对应的方块前缀和后缀。
- 从每个前缀和后缀中获取前两个元素（或者仅获取前一个元素，如果 window 足够小）。
- 在（最多）四个值中，确定哪个是 second-largest 和 return。
通过一些预处理，我们确实可以设置我们的 windows 来回答 "what are the two largest elements in each suffix?" 和 "what are the two largest elements in each prefix?" 形式的查询你可以有点认为这是一个动态的编程题，设置如下：
- 对于任何长度为 1 的 prefix/suffix，将单个值存储在 prefix/suffix 中。
- 对于长度为 2 的任何 prefix/suffix，前两个值是两个元素本身。
- 对于任何更长的前缀或后缀，可以通过将较小的前缀或后缀扩展为单个元素来形成该前缀或后缀。要确定那个较长 prefix/suffix 的前两个元素，请比较用于将范围扩展到前两个元素的元素和 select 该范围外的前两个元素。
请注意，填写每个 prefix/suffix 的前两个值需要时间 O(1)。这意味着我们可以在 O(w) 时间内填写任何 window，因为有 w 个条目要填写。而且，由于总共有 O(n / w) windows，因此总时间填写这些条目所需的时间是 O(n)，因此我们的整体算法运行时间为 O(n)。
至于 space 用法：如果您急切地计算整个数组中的所有 prefix/suffix 值，则需要使用 space O(n) 来保存所有内容。但是，由于在任何时间点我们只关心两个 windows，您也可以只在需要时才计算 prefixes/suffixes。这将只需要 space O(w)，这真的非常好！
选项 3：使用巧妙数据结构的 O(n) 时间解决方案
最后一种方法与上述方法完全等同，但框架不同。
可以 build a queue that allows for constant-time querying of its maximum element. The idea behind this queue - beginning with a stack that supports efficient find-max 然后在 two-stack 队列构造中使用它 - 可以很容易地推广到构建一个队列，使 constant-time 可以访问 second-largest元素。为此，您只需调整堆栈结构以存储每个时间点的前两个元素，而不仅仅是最大的元素。
如果你有这样的队列，在任何 window 中查找 second-max 值的算法非常快：用前 w 个元素加载队列，然后重复使元素出列（将某些内容移出 window）并将下一个元素排入队列（将某些内容移入 window）。这些操作中的每一个都需要分摊 O(1) 时间才能完成，因此这总体上需要时间 O(n)。
有趣的事实 - 如果您查看此队列实现在此特定用例中实际执行的操作，您会发现它完全等同于上述策略。一个堆栈对应于前一个块的后缀，另一个对应于下一个块的前缀。
最后一个策略是我个人最喜欢的，但不可否认这只是我自己的数据结构偏见。
希望对您有所帮助！
所以给定一个数组和一个 window 大小，我需要在每个 window 中找到第二大的。蛮力解决方案非常简单，但我想使用动态规划找到一个有效的解决方案
当我对大数组尝试暴力破解时超时，所以我需要找到更好的解决方案。我的解决方案是通过对它们进行排序并获取第二个元素来在每个滑动中找到第二大window，我知道某些数据结构可以更快地排序，但我想知道是否有更好的方法[=11] =]
有一个相对简单的动态编程O(n^2)解决方案：
为子集上的聚合值构建经典金字塔结构（您将下面两对的值组合起来以进行上面的每个步骤），在其中跟踪最大的 2 个值（及其位置），然后简单地保留最大的 2 个值4 个组合值中的一个（由于重叠而在实践中较少，使用位置来确保它们实际上不同）。然后，您只需从具有正确滑动 window 大小的图层中读取第二大值。
所以就拿一个像集合这样的数据结构，有序的存储数据。 就像如果你在集合上存储 4 2 6 它将存储为 2 4 6.
那么算法是什么：
让，
数组 = [12,8,10,11,4,5] window尺寸=4
首先window=[12,8,10,11] 设置=[8,10,11,12]
如何获得第二高：
- 从集合中移除最后一个元素并存储在容器中。 set=[8,10,11],contaniner = 12
- 删除后，集合的当前最后一个元素是当前集合的第二大元素 window.
- 再次将容器中存放的移除元素放到set中，set=[8,10,11,12]
现在转移你的 window，
- 从集合中删除 12 并添加 4.
- 现在您将获得新的 window 并设置。
- 检查类似的过程。
在集合中删除和添加元素的复杂度约为 log(n)。
一招：
如果你总是想以降序存储数据，那么你可以将数据乘以-1来存储数据。当你弹出数据时，通过乘以-1来使用它。
我们可以使用双端队列来解决 O(n) 的问题。队列的前面将有更大的（和更早看到的）元素：
0 1 2 3 4 5
{12, 8,10,11, 4, 5}
window size: 3
i queue (stores indexes)
- -----
0 0
1 1,0
2 2,0 (pop 1, then insert 2)
output 10
remove 0 (remove indexes not in
the next window from the front of
the queue.)
3 3 (special case: there's only one
smaller element in queue, which we
need so keep 2 as a temporary variable.)
output 10
4 4,3
output 10
remove 2 from temporary storage
5 5,3 (pop 4, insert 5)
output 5
"pop" 和 "remove from front" 分别是 while A[queue_back] <= A[i] 和 while queue_front is outside next window（尽管队列中只剩下一个较小的元素表示复杂）。我们从队列的前面输出由第二个元素索引的数组元素（尽管我们的前面可能有一个特殊的临时朋友也曾经在前面；这个特殊的朋友一旦代表一个元素在外面就被丢弃window 或小于由前面第二个队列元素索引的元素）。双端队列的复杂度为 O(1)，可以从前端或后端移除。我们只插在后面。
根据 templatetypedef 在评论中的要求："how you determine which queue operations to use?" 在每次迭代中，使用索引 i，在将其插入队列之前，我们 (1) 从队列后面弹出每个元素表示数组中小于或等于 A[i] 的元素，并且 (2) 从队列的前面移除每个索引在当前 window 之外的元素。 （如果在（1）中，我们只剩下一个较小或相等的元素，我们将它保存为一个临时变量，因为它是当前第二大的。）
有很多方法可以解决这个问题。这里有几个选项。在下文中，我将让 n 表示输入数组中的元素数量，w 表示 window 大小。
选项 1：一个简单的 O(n log w) 时间算法
一个选择是维护一个平衡的二叉搜索树，其中包含当前 window 中的所有元素，包括重复元素。向这个 BST 中插入一些东西需要时间 O(log w)，因为 window 中总共只有 w 个元素，出于同样的原因，删除一个元素也需要时间 O(log w)。这意味着将 window 滑动一个位置需要时间 O(log w).
要在 window 中找到 second-largest 元素，您只需要应用 standard algorithm for finding the second-largest element in a BST，这在具有 w 个元素的 BST 中需要时间 O(log w) .
这种方法的优点是，在大多数编程语言中，编写这个代码会相当简单。它还利用了一堆 well-known 标准技术。缺点是运行时不是最优的，我们可以改进它。
选项 2：O(n) prefix/suffix 算法
这里有一个 linear-time 解决方案，实施起来相对简单。在高层次上，该解决方案的工作原理是将数组拆分为一系列块，每个块的大小为 w。例如，考虑以下数组：
31 41 59 26 53 58 97 93 23 84 62 64 33 83 27 95 02 88 41 97
假设 w = 5。我们将数组拆分为大小为 5 的块，如下所示：
31 41 59 26 53 | 58 97 93 23 84 | 62 64 33 83 27 | 95 02 88 41 97
现在，假设在这个数组的某处放置一个长度为 5 的 window，如下所示：
31 41 59 26 53 | 58 97 93 23 84 | 62 64 33 83 27 | 95 02 88 41 97
|-----------------|
请注意，此 window 将始终由一个块的后缀和后跟另一个块的前缀组成。这很好，因为它允许我们解决一个稍微简单的问题。想象一下，我们可以通过某种方式有效地确定任何块的任何前缀或后缀中的两个最大值。然后我们可以在任何 window 中找到 second-max 值，如下所示：
- 找出window对应的方块前缀和后缀。
- 从每个前缀和后缀中获取前两个元素（或者仅获取前一个元素，如果 window 足够小）。
- 在（最多）四个值中，确定哪个是 second-largest 和 return。
通过一些预处理，我们确实可以设置我们的 windows 来回答 "what are the two largest elements in each suffix?" 和 "what are the two largest elements in each prefix?" 形式的查询你可以有点认为这是一个动态的编程题，设置如下：
- 对于任何长度为 1 的 prefix/suffix，将单个值存储在 prefix/suffix 中。
- 对于长度为 2 的任何 prefix/suffix，前两个值是两个元素本身。
- 对于任何更长的前缀或后缀，可以通过将较小的前缀或后缀扩展为单个元素来形成该前缀或后缀。要确定那个较长 prefix/suffix 的前两个元素，请比较用于将范围扩展到前两个元素的元素和 select 该范围外的前两个元素。
请注意，填写每个 prefix/suffix 的前两个值需要时间 O(1)。这意味着我们可以在 O(w) 时间内填写任何 window，因为有 w 个条目要填写。而且，由于总共有 O(n / w) windows，因此总时间填写这些条目所需的时间是 O(n)，因此我们的整体算法运行时间为 O(n)。
至于 space 用法：如果您急切地计算整个数组中的所有 prefix/suffix 值，则需要使用 space O(n) 来保存所有内容。但是，由于在任何时间点我们只关心两个 windows，您也可以只在需要时才计算 prefixes/suffixes。这将只需要 space O(w)，这真的非常好！
选项 3：使用巧妙数据结构的 O(n) 时间解决方案
最后一种方法与上述方法完全等同，但框架不同。
可以 build a queue that allows for constant-time querying of its maximum element. The idea behind this queue - beginning with a stack that supports efficient find-max 然后在 two-stack 队列构造中使用它 - 可以很容易地推广到构建一个队列，使 constant-time 可以访问 second-largest元素。为此，您只需调整堆栈结构以存储每个时间点的前两个元素，而不仅仅是最大的元素。
如果你有这样的队列，在任何 window 中查找 second-max 值的算法非常快：用前 w 个元素加载队列，然后重复使元素出列（将某些内容移出 window）并将下一个元素排入队列（将某些内容移入 window）。这些操作中的每一个都需要分摊 O(1) 时间才能完成，因此这总体上需要时间 O(n)。
有趣的事实 - 如果您查看此队列实现在此特定用例中实际执行的操作，您会发现它完全等同于上述策略。一个堆栈对应于前一个块的后缀，另一个对应于下一个块的前缀。
最后一个策略是我个人最喜欢的，但不可否认这只是我自己的数据结构偏见。
希望对您有所帮助！