自己做视频网站能赚钱吗,wordpress 导航调用代码,阿里云手机网站建设多少钱,平面图用什么软件做前言
本专栏旨在通过分类学习算法#xff0c;使您能够牢固掌握不同算法的理论要点。通过策略性地练习精选的经典题目#xff0c;帮助您深度理解每种算法#xff0c;避免出现刷了很多算法题#xff0c;还是一知半解的状态 专栏导航
二分查找回溯#xff08;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]在这个例子中我们定义了一个 MonotonicQueue 类来模拟单调递减队列并在滑动窗口中使用它来找到每个窗口的最大值。当新元素加入时队列中所有小于新元素的值都会被移除以保持队列的单调递减性。当窗口滑动时如果队头的元素是窗口最左边即将移出窗口的值则将其从队列中移除。 实战练习
购买水果需要的最少金币数
你在一个水果超市里货架上摆满了玲琅满目的奇珍异果。
给你一个下标从 1 开始的数组 prices 其中 prices[i] 表示你购买第 i 个水果需要花费的金币数目。
水果超市有如下促销活动
如果你花费 price[i] 购买了水果 i 那么接下来的 i 个水果你都可以免费获得。 注意 即使你 可以 免费获得水果 j 你仍然可以花费 prices[j] 个金币去购买它以便能免费获得接下来的 j 个水果。
请你返回获得所有水果所需要的 最少 金币数。
示例 1 输入prices [3,1,2] 输出4
解释你可以按如下方法获得所有水果
花 3 个金币购买水果 1 然后免费获得水果 2 。花 1 个金币购买水果 2 然后免费获得水果 3 。免费获得水果 3 。 注意虽然你可以免费获得水果 2 但你还是花 1 个金币去购买它因为这样的总花费最少。 购买所有水果需要最少花费 4 个金币。
示例 2 输入prices [1,10,1,1] 输出2
解释你可以按如下方法获得所有水果
花 1 个金币购买水果 1 然后免费获得水果 2 。免费获得水果 2 。花 1 个金币购买水果 3 然后免费获得水果 4 。免费获得水果 4 。 购买所有水果需要最少花费 2 个金币。
提示 1 prices.length 1000 1 prices[i] 105
官方题解 环形子数组的最大和
给定一个长度为 n 的环形整数数组 nums 返回 nums 的非空 子数组 的最大可能和 。
环形数组 意味着数组的末端将会与开头相连呈环状。形式上 nums[i] 的下一个元素是 nums[(i 1) % n] nums[i] 的前一个元素是 nums[(i - 1 n) % n] 。
子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上对于子数组 nums[i], nums[i 1], …, nums[j] 不存在 i k1, k2 j 其中 k1 % n k2 % n 。
示例 1 输入nums [1,-2,3,-2] 输出3 解释从子数组 [3] 得到最大和 3
示例 2 输入nums [5,-3,5] 输出10 解释从子数组 [5,5] 得到最大和 5 5 10
示例 3 输入nums [3,-2,2,-3] 输出3 解释从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3
提示 n nums.length 1 n 3 * 104 -3 * 104 nums[i] 3 * 104
官方题解
