单调队列

单调队列是一种特殊的数据结构，它结合了“单调”和“队列”的特点。这里的“单调”指的是队列中的元素按照递增或递减的顺序排列，而“队列”则意味着元素只能从队列的头部或尾部进行操作。

单调队列的主要作用是用于求解区间最值问题，特别是在处理滑动窗口类问题时，它能够以O(n)的时间复杂度高效地找到答案。实现单调队列通常需要维护一个双向队列（deque），以下是单调队列的基本操作步骤：

当新元素加入时，从队列尾部开始，移除那些贡献更小、代价更大的不再需要的元素。
如果对元素有额外的约束条件（如滑动窗口大小限制），需要在队列头部删除不满足条件的元素。
通常情况下，队列头部的元素就是当前队列维护的最优解。

例题介绍

239 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
1 [3  -1  -3] 5  3  6  7       3
1  3 [-1  -3  5] 3  6  7       5
1  3  -1 [-3  5  3] 6  7       5
1  3  -1  -3 [5  3  6] 7       6
1  3  -1  -3  5 [3  6  7]      7
提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

问题理解

给定一个整数数组 nums 和一个大小为 k 的滑动窗口，窗口从数组的最左侧移动到最右侧。返回滑动窗口中的最大值。

解题思路

为了找到每个滑动窗口中的最大值，我们可以使用一个双向队列（deque）来维护一个可能成为窗口最大值的元素的索引。以下是详细步骤：

初始化队列：开始时，队列为空。
遍历数组：对于数组中的每个元素 nums[i]（其中 i 是当前元素的索引），执行以下操作：
- 清理队列：从队列尾部开始，移除所有那些 nums[i] 比它们大的元素的索引，因为这些元素不可能成为任何窗口的最大值了。这是因为它们既不如 nums[i] 大，也不如 nums[i] 新（即距离窗口右端点的距离更远）。这样可以保证队列中剩余的元素都是潜在的最大值候选者，并且它们的顺序是从大到小排列的。
  c++
```
while (!q.empty() && nums[q.back()] <= nums[i]) {
    q.pop_back();
}
```
- 加入当前元素：将当前元素的索引 i 加入队列。
  c++
```
q.push_back(i);
```
- 保持窗口长度：如果队列头部的元素的索引与当前索引 i 的距离大于 k，则该元素已经不在当前窗口中了，需要从队列头部移除。这确保了队列中只保留当前窗口内的元素索引。
  c++
```
while (q.front() <= i - k) {
    q.pop_front();
}
```
- 记录答案：如果当前索引 i 已经大于或等于 k - 1，说明窗口已经填满，此时队列头部的元素就是当前窗口的最大值，将其加入结果数组。
  c++
```
if (i >= k - 1) {
    ans.push_back(nums[q.front()]);
}
```

代码实现

查看代码

c++

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        deque<int> q; // 双向队列，用于存储可能成为最大值的元素的索引
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            // 移除所有比当前元素小的元素
            while (!q.empty() && nums[q.back()] <= nums[i]) {
                q.pop_back();
            }
            // 将当前元素的索引加入队列
            q.push_back(i);
            // 移除不在当前窗口内的元素
            while (q.front() <= i - k) {
                q.pop_front();
            }
            // 如果窗口已填满，记录当前窗口的最大值
            if (i >= k - 1) {
                ans.push_back(nums[q.front()]);
            }
        }
        return ans;
    }
};

单调队列优化DP

利用单调队列来优化动态规划的状态转移。

1425 带限制的子序列和
给你一个整数数组 nums 和一个整数 k ，请你返回非空子序列元素和的最大值，子序列需要满足：子序列中每两个相邻的整数 nums[i] 和 nums[j] ，它们在原数组中的下标 i 和 j 满足 i < j 且 j - i <= k 。
数组的子序列定义为：将数组中的若干个数字删除（可以删除 0 个数字），剩下的数字按照原本的顺序排布。
示例 1：
输入：nums = [10,2,-10,5,20], k = 2
输出：37
解释：子序列为 [10, 2, 5, 20] 。
提示：
1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

在解决这个问题时，我们可以采用动态规划的方法。

首先，定义 f[i] 为在数组的前 i 个数中进行选择，并且恰好选择了第 i 个数时，可以得到的最大子序列和。

状态转移方程有两个部分：

如果只选择第 i 个数，那么 f[i] = nums[i]。
如果选择了第 i 个数，并且从之前的 k 个数中选择一个，使得子序列和最大，那么 f[i] = max(f[j]) + nums[i]，其中 j < i 且 i - j <= k。

直接实现这个状态转移方程的时间复杂度是 O(nk)，这在数据量大时会导致超时。然而，我们可以通过单调队列来优化这个过程。

观察发现，这个问题的状态转移与滑动窗口最大值问题非常相似，都是在长度为 k 的区间内求最大值。因此，我们可以使用单调队列来维护一个可能的最大子序列和的索引。

以下是使用单调队列优化动态规划的步骤：

初始化一个双向队列 q 和一个数组 f，其中 f[0] = nums[0]。
遍历数组，对于每个索引 i，执行以下操作：
- 去头：如果队列头部的索引与当前索引 i 的距离大于 k，则从队列头部移除。
- 择优：计算 f[i]，它等于队列头部索引对应的 f 值（如果为正）加上 nums[i]。
- 去尾：如果当前计算的 f[i] 大于或等于队列尾部索引对应的 f 值，则从队列尾部移除，直到找到一个更大的 f 值或队列为空。
- 加入：将当前索引 i 加入队列。

最后，返回数组 f 中的最大值，即为所求的最大子序列和。

以下是优化后的代码实现：

查看代码

c++

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> f(n);
        f[0] = nums[0];
        deque<int> q;
        q.push_back(0);
        for (int i = 1; i < n; i++) {
            // 去头
            while (!q.empty() && i - q.front() > k) q.pop_front();
            // 择优
            f[i] = max(f[q.front()], 0) + nums[i];
            // 去尾
            while (!q.empty() && f[i] >= f[q.back()]) q.pop_back();
            // 加入
            q.push_back(i);
        }
        // 返回最大子序列和
        return *max_element(f.begin(), f.end());
    }
};

通过这种方式，我们将动态规划的状态转移时间复杂度从 O(nk) 降低到了 O(n)，大大提高了算法的效率。

单调队列 ​

例题介绍 ​

问题理解 ​

解题思路 ​

代码实现 ​

单调队列优化DP ​