每日算法系列【LeetCode 239】滑动窗口最大值

发布网友发布时间：2024-10-15 16:48

共1个回答

热心网友时间：2024-10-18 03:35

给定数组 nums，滑动窗口大小为 k，从数组左端滑动至右端。每次滑动窗口仅前进一位，寻找滑动窗口中的最大值。

双端单调队列解法：理解最值转移特性，若新元素 a 在 b 前且 a < b，则 a 后续不可成为最大值。使用双端队列维护单调递减序列，队首元素始终为当前窗口最大值。遍历过程中，保持队列两端的元素符合单调递减性质，去除非最大值元素，以适应窗口滑动。

分块法解法：将数组划分为若干大小为 k 的块，块间最大值已知，求区间最大值时只需合并块最大值。块大小为 k 正好覆盖完整块区间，块间最大值用于区间计算。块大小设为 k 时，区间 [i, j] 或完全包含完整块，或跨越相邻块，合并块最大值即得区间最大值。

实现细节：C++ 中 deque 提供双端队列功能，数组模拟实现逻辑相似，Python 中 deque 同样适用。分块法在 C++、Python 中亦有实现。

总结：双端单调队列和分块法是解决滑动窗口最大值问题的有效方法。队列解法简洁高效，分块法通过预处理块最大值优化区间查询，不同解法各有优势，适合不同场景选用。