当前位置：首页 > news >正文

丹徒网站建设哪家好永济做网站单价

news 2025/11/7 7:11:53

丹徒网站建设哪家好,永济做网站单价,怎么做网站卖东西,网站平台建设费计入什么科目前言本专栏旨在通过分类学习算法，使您能够牢固掌握不同算法的理论要点。通过策略性地练习精选的经典题目，帮助您深度理解每种算法，避免出现刷了很多算法题，还是一知半解的状态专栏导航二分查找回溯（Backtracking&…

前言

本专栏旨在通过分类学习算法，使您能够牢固掌握不同算法的理论要点。通过策略性地练习精选的经典题目，帮助您深度理解每种算法，避免出现刷了很多算法题，还是一知半解的状态

专栏导航

二分查找
回溯（Backtracking）
双指针
滑动窗口
深度优先搜索
广度优先搜索
贪心算法
单调队列
堆（Heap）
分治（Divide and Conquer）
动态规划

算法解析

单调队列是一种特殊的队列数据结构，其主要特点是保持队列元素的单调性（单调递增或单调递减）。在单调队列中，新元素的加入可能会导致队列中的一些元素被移除，以维护队列的单调性。

单调队列通常用于解决滑动窗口类问题，如寻找窗口内的最大值或最小值。使用单调队列能够在常数时间内获取窗口的最大或最小元素，从而有效地优化算法的时间复杂度。

以下是单调队列的两种主要操作：

入队（Push）：
当新元素加入队列时，从队列尾部开始，移除所有破坏队列单调性的元素，然后将新元素加入队列尾部。对于单调递增队列，如果新元素小于队尾元素，则队尾元素被移除；对于单调递减队列，如果新元素大于队尾元素，则队尾元素被移除。
出队（Pop）：
当需要移除队列头部元素时（例如滑动窗口移动导致窗口头部元素不再属于当前窗口），如果队头元素等于需要移除的元素，则将其出队。

单调队列可以用双端队列（deque）来实现，因为双端队列允许从两端高效地添加和移除元素。

下面是一个使用 Python 中的 collections.deque 实现单调递减队列的示例，该队列用于找到滑动窗口的最大值：

from collections import dequeclass MonotonicQueue:def __init__(self):self.deque = deque()def push(self, value):# 移除所有小于即将入队的值的元素while self.deque and self.deque[-1] < value:self.deque.pop()self.deque.append(value)def max(self):# 队列的最大值始终位于队头return self.deque[0]def pop(self, value):# 如果队头元素是即将移除的值，则出队if self.deque and self.deque[0] == value:self.deque.popleft()# 示例：滑动窗口最大值
def max_sliding_window(nums, k):window = MonotonicQueue()result = []for i, value in enumerate(nums):if i < k - 1:window.push(value)else:# 滑动窗口向右移动window.push(value)result.append(window.max())  # 记录当前窗口的最大值# 移除窗口最左边的值window.pop(nums[i - k + 1])return result# 使用示例
nums = [1,3,-1,-3,5,3,6,7]
k = 3
print(max_sliding_window(nums, k))  # 输出 [3,3,5,5,6,7]