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

前言

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

---

专栏导航

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

官方题解