[功能]添加使用双端队列的滑动窗口最大值算法

我提议在C++中增加一个使用Deque(monotonic deque技术)的滑动窗口最大算法的实施.

鉴于一个阵列和一个窗口大小K,这个算法在大小K的每一个相接窗口中,在跨阵列滑动时,在O(N)时间中,而不是在天真的O(N*K)野蛮-武力方法中,高效地找到最大元素.

算法如何运作:

保持一个存储数组元素指数的分级,并按其值的递减顺序进行保存。 对于每个新要素: 从值小于当前元素的矩形后方删除索引( 当当前元素在窗口中时, 它们永远不会是最大值) 。 如果索引已滑出当前窗口,则删除前面的索引。 将当前索引推到后. 一旦第一个窗口被填满,德克前方就是该窗口的最大值.

拟议变动:

在数据 结构/(或其他/,以最符合现有结构者为准-打开维护者放置指导)下添加滑动 窗口 最大.cpp 使用 std:deque 来维持有用元素索引的完整执行 清晰的注释来解释单调的变体 文件中的自我测试(遵循Repo现有的基于文件的断言测试风格),涵盖标准案例,K等于数组大小,K=1并重复元素.

复杂性分析:

时间复杂度:O(N) -- -- 每个元素最多一次被推出并被弹出 空间复杂度:O(K) -- -- 一次最多持有K指数

我将确保执行遵循存储器的编码风格(clang-format/clang-tidy),并在开启公关前通过CI. 我会着手着手研究 并打开公关 引用这个问题.