本文几乎都是由ChatGPT生成，包括后面的例题的题解。
代码是我根据题解自己实现的。
几天的使用下来，我发现ChatGPT是一个强力的算法竞赛的好帮手，所以有了这篇文章作为试水。
单调队列是什么?
单调队列是一种数据结构，它是一个具有单调性的队列。这意味着队列中的元素必须满足某种单调性，比如单调递增或单调递减。单调队列可以用来解决许多不同的问题，包括求最大值、最小值和优化算法的时间复杂度。
如何用单调队列求滑动窗口最大值
单调队列可以用来求解滑动窗口问题，其中窗口内的最大值是我们感兴趣的。在滑动窗口中，我们不断地将新的元素添加到队列的末尾，并将队列的头部元素删除，使得窗口的大小保持不变。
求滑动窗口最大值的关键在于如何维护队列中的元素的单调性。在这种情况下，我们可以使用一个单调递减的队列，这意味着队列中的元素是按照从大到小的顺序排列的。在添加新元素时，我们会把它与队列中所有比它小的元素都删除，然后再将它添加到队列的末尾。这样，队列中始终保持着一组单调递减的元素，其中第一个元素就是当前窗口中的最大值。
假设我们有一个数组 A = [3, 4, 2, 5, 1, 6]，。
当第一个元素（A[0] = 3）被添加到窗口中时，队列中只有一个元素，即 3。
当第二个元素（A[1] = 4）被添加到窗口中时，此时，我们比较 4 和队列中末尾的元素， 很明显比3大，因此队列中的元素变为 [4]。
当第三个元素（A[2] = 2）被添加到窗口中时，此时，我们比较 2 和队列中末尾的元素，发现 2 比 4 小，所以不会删除 4，队列中的元素变为 [4, 2]。
当第四个元素（A[3] = 5）被添加到窗口中时，。此时，我们比较 5 和队列中末尾的元素，发现 5 比 4 和 2都 大，所以会连续删除 4 和 2。队列中的元素变为 [5]
继续按照这种方式，我们可以计算出整个滑动窗口的最大值序列为 [4, 5, 5, 6]，
注意：因为滑动窗口的大小不超过 3，因此在具体的实现中，我们在每一步开始前，比较队头元素与当前元素的距离是否已经超出窗口了，如果已经超过，则需要踢掉队头元素。具体可以看代码实现。
这样，我们就可以利用单调队列来求解滑动窗口最大值问题，这样的时间复杂度为 O(n)，其中 n 是数组 A 的长度。
代码实现(Python / C++)
def max_in_sliding_window(nums, k):
if not nums:
return []
result = []
window = deque()
for i, num in enumerate(nums):
# 移除队列中小于当前值的元素
while window and nums[window[–1]] < num:
window.pop()
# 移除队列中窗口已经滑出的元素
if window and i – window[0] >= k:
window.popleft()
# 将当前值加入队列
window.append(i)
# 将当前窗口的最大值加入结果列表
if i >= k – 1:
result.append(nums[window[0]])
return result
# 测试用例
nums = [1, 3, –1, –3, 5, 3, 6, 7]
k = 3
print(max_in_sliding_window(nums, k)) # 输出 [3, 3, 5, 5, 6, 7]
vector<int> max_in_sliding_window(vector<int>& nums, int k) {
if (nums.empty()) return {};
vector<int> result;
deque<int> window;
for (int i = 0; i < nums.size(); i++) {
// 移除队列中小于当前值的元素
while (!window.empty() && nums[window.back()] < nums[i]) {
window.pop_back();
}
// 移除队列中窗口已经滑出的元素
if (!window.empty() && i – window.front() >= k) {
window.pop_front();
}
// 将当前值加入队列
window.push_back(i);
// 将当前窗口的最大值加入结果列表
if (i >= k – 1) {
result.push_back(nums[window.front()]);
}
}
return result;
}
int main() {
// 测试用例
vector<int> nums = {1, 3, –1, –3, 5, 3, 6, 7};
int k = 3;
vector<int> result = max_in_sliding_window(nums, k);
for (int num : result) {
cout << num << ” “;
} // 输出 3 3 5 5 6 7
}
P1725 琪露诺
题目描述
在幻想乡，琪露诺是以笨蛋闻名的冰之妖精。
某一天，琪露诺又在玩速冻青蛙，就是用冰把青蛙瞬间冻起来。但是这只青蛙比以往的要聪明许多，在琪露诺来之前就已经跑到了河的对岸。于是琪露诺决定到河岸去追青蛙。
小河可以看作一列格子依次编号为 00 到 NN，琪露诺只能从编号小的格子移动到编号大的格子。而且琪露诺按照一种特殊的方式进行移动，当她在格子 ii 时，她只移动到区间 [i+L,i+R][i+L,i+R]中的任意一格。你问为什么她这么移动，这还不简单，因为她是笨蛋啊。
每一个格子都有一个冰冻指数 AiA_i，编号为 00 的格子冰冻指数为 00。当琪露诺停留在那一格时就可以得到那一格的冰冻指数 AiA_i。琪露诺希望能够在到达对岸时，获取最大的冰冻指数，这样她才能狠狠地教训那只青蛙。
但是由于她实在是太笨了，所以她决定拜托你帮它决定怎样前进。
开始时，琪露诺在编号 00 的格子上，只要她下一步的位置编号大于 NN 就算到达对岸。
输入格式
第一行三个正整数 N,L,RN, L, R。
第二行共 N+1N+1 个整数，第 ii 个数表示编号为 i−1i-1 的格子的冰冻指数 Ai−1A_{i-1}。
输出格式
一个整数，表示最大冰冻指数。
样例 #1
样例输入 #1
0 12 3 11 7 -2
样例输出 #1
提示
对于 60%60\% 的数据，N≤104N \le 10^4。
对于 100%100\% 的数据，N≤2×105N \le 2\times 10^5，−103≤Ai≤103-10^3 \le A_i\le 10^3 ，1≤L≤R≤N1 \le L \le R \le N 。数据保证最终答案不超过 231−12^{31}-1。
思路
一种可能的解决方案是使用动态规划。
我们可以定义状态 f[i]f[i] 表示到达位置 ii 时可以获得的最大价值和。
然后我们可以通过以下方式转移状态：
f[i]=max(f[j]+A[i])(i−R≤j≤i−L)f[i] = \max(f[j] + A[i]) \quad (i – R \leq j \leq i – L)
这意味着如果我们在位置 ii 处，我们可以查看位置 [i−R,i−L][i – R, i – L] 中的所有位置 jj，并选择使f[i]f[i] 最大的位置。
我们可以使用一个循环枚举位置 ii，然后使用一个循环枚举位置 jj，并计算 f[i]f[i] 的值。
这是一种可能的解决方案，但是它有一个缺点，即时间复杂度为 O(N2)O(N^2)。
另一种可能的解决方案是优化上述算法，将时间复杂度降低到 O(N)O(N)。
我们可以使用一个单调队列来维护 f[j]f[j] 的值。单调队列可以在每次计算 f[i]f[i] 时让我们快速找到 [i−R,i−L][i – R, i – L] 中的最大值。
首先我们枚举位置 ii，然后将 f[j]f[j] 的值添加到单调队列中。每次添加一个新值时，我们需要从队列中删除所有小于等于当前值的值，以维护队列的单调性。
然后，当计算 f[i]f[i] 时，我们可以查看队列的队首元素，它是队列中的最大值。我们可以将它与 f[i]f[i] 相加，并将结果存储在 f[i]f[i] 中。
同时，我们需要从队列中删除所有下标小于 i−Ri – R的元素，以维护队列的长度。
显然我们可以在枚举到 N”>i+R>Ni + R > N 的时候，计算结果，即 N)”>ans=max(f[i])(i+R>N)ans = max(f[i]) (i + R > N)
该算法的时间复杂度为O(N)O(N)，因为每个位置 ii 只会被枚举一次，并且每次操作都只需要 O(1)O(1) 的时间。
总的来说，这是一种有效的优化方法，可以将算法的时间复杂度从 O(N2)O(N^2) 降低到 O(N)O(N)。
int N, L, R;
std::cin >> N >> L >> R;
std::vector<int> a(N + 1);
for (int& x : a) std::cin >> x;
const int inf = 2e9;
std::vector<int> dp(N + 1, –inf);
std::deque<int> dq;
dp[0] = 0;
int res = –inf;
for (int i = L; i <= N; i++) {
int right_bound = i – L, left_bound = i – R;
while (!dq.empty() && dp[dq.back()] <= dp[right_bound]) dq.pop_back();
dq.push_back(right_bound);
while (!dq.empty() && dq.front() < left_bound) dq.pop_front();
dp[i] = dp[dq.front()] + a[i];
if (i + R > N) res = std::max(res, dp[i]);
}
std::cout << res << \n;
}
相关文章
