【面试高频算法解析】算法练习8 单调队列

2024-01-09 15:45:18

前言

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


专栏导航

  1. 二分查找
  2. 回溯(Backtracking)
  3. 双指针
  4. 滑动窗口
  5. 深度优先搜索
  6. 广度优先搜索
  7. 贪心算法
  8. 单调队列
  9. 堆(Heap)
  10. 分治(Divide and Conquer)
  11. 动态规划

算法解析

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

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

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

  1. 入队(Push)
    当新元素加入队列时,从队列尾部开始,移除所有破坏队列单调性的元素,然后将新元素加入队列尾部。对于单调递增队列,如果新元素小于队尾元素,则队尾元素被移除;对于单调递减队列,如果新元素大于队尾元素,则队尾元素被移除。

  2. 出队(Pop)
    当需要移除队列头部元素时(例如滑动窗口移动导致窗口头部元素不再属于当前窗口),如果队头元素等于需要移除的元素,则将其出队。

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

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

from collections import deque

class 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???????

官方题解

文章来源:https://blog.csdn.net/sinat_41883985/article/details/135346986
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。