使用单调队列

单调队列是一种主要用于解决滑动窗口类问题的数据结构. 时间复杂度为 O (n).

其原理就是一句话，当队列中前面的数比后面的小 (大) 时，前面的数出队.

实现上，维护一个双向队列， 遍历时仅当一个元素可能成为某区间的最值时才保留它.

代码


import collections
monotonous_queue = collections.deque()
class Item(object):
    def __init__(self, i, v):
        self.index = i
        self.value = v


items: tuple[Item] = tuple()


def front():
    return monotonous_queue[0]

def back():
    return monotonous_queue[-1]

for i in range(0, n):
    if not monotonous_queue.empty() and top().index <= i - length:
        monotonous_queue.leftpop()
    t = items[i]
    while not monotonous_queue.empty() and back().value < t.value:
        monotonous_queue.pop()
    monotonous_queue.push(t)
#include <deque>
struct Item{
    size_t index;
    int value;
} items[n];
deque<Item> monotonous_queue;
for(size_t i = 0; i < n; i++){
    if(!monotonous_queue.empty() && monotonous_queue.front().index <= i - length)
        monotonous_queue.pop_front();
    while(!monotonous_queue.empty() && monotonous_queue.back().value < items[i].value)
        monotonous_queue.pop_back();
    monotonous_queue.push_back(items[i]);
}