Tag: sliding-window
-
alg: 单调队列和滑动窗口算法
单调队列 给定一个长度为 n 的数组，需要输出每连续 k 个数（A[i, i+k-1]）中的最大值，可以在 O(n) 时间内做完吗？ 一个思路就是动态地维护一个队列，在任何时刻 i 都满足 队列中的元素来自 A[i, i+k-1] A[s] 在队列中，当且仅当 A(s, i+k-1] 中的元素都小于 A[s]。特别地，A[i+k-1] 一定在队尾。…
单调队列 给定一个长度为 n 的数组，需要输出每连续 k 个数（A[i, i+k-1]）中的最大值，可以在 O(n) 时间内做完吗？ 一个思路就是动态地维护一个队列，在任何时刻 i 都满足 队列中的元素来自 A[i, i+k-1] A[s] 在队列中，当且仅当 A(s, i+k-1] 中的元素都小于 A[s]。特别地，A[i+k-1] 一定在队尾。…