单调队列深度解析(下)

在《单调队列深度解析(上)》中，我已经对单调队列的基本定义、算法思想、结构性质、使用步骤以及基本模板进行了详细的介绍。在本文中，我将深入探讨单调队列的进阶应用，包括在图论、动态规划等复杂场景中的使用，帮助大家对单调队列有更深刻的理解和更灵活的运用。

一、单调队列在图论中的应用

1. 问题背景

在图论中，有时我们需要在满足一定条件的路径上寻找最值。单调队列可以帮助我们在动态更新路径信息的过程中，高效地维护局部最值，从而优化算法的时间复杂度。

2. 示例问题：最短路径上的最大边权

假设有一个带权无向图 $G=(V,E)$，我们要从起点 $s$ 到终点 $t$ 寻找一条最短路径，并且我们关心这条最短路径上的最大边权。

算法思路

我们可以使用 Dijkstra 算法的变种来解决这个问题。在 Dijkstra 算法的优先队列中，我们通常存储的是到某个节点的最短距离。而在这里，我们除了存储最短距离外，还需要维护从起点到该节点的最短路径上的最大边权。在更新路径信息时，使用单调队列来维护这个最大边权。

代码实现（Python）

import heapq
from collections import dequedef shortest_path_max_edge_weight(graph, start, end):n = len(graph)dist = [float('inf')] * nmax_edge = [0] * ndist[start] = 0pq = [(0, 0, start)]  # (distance, max_edge_weight, node)while pq:d, me, node = heapq.heappop(pq)if d > dist[node]:continueif node == end:return mefor neighbor, weight in graph[node]:new_dist = d + weightnew_max_edge = max(me, weight)if new_dist < dist[neighbor]:dist[neighbor] = new_distmax_edge[neighbor] = new_max_edgeheapq.heappush(pq, (new_dist, new_max_edge, neighbor))return -1# 示例图的邻接表表示
graph = [[(1, 2), (2, 4)],[(0, 2), (2, 1), (3, 7)],[(0, 4), (1, 1), (3, 3)],[(1, 7), (2, 3)]
]
start = 0
end = 3
print(shortest_path_max_edge_weight(graph, start, end))

二、单调队列在动态规划中的应用

1. 问题背景

动态规划是解决许多优化问题的常用方法，但在某些情况下，状态转移的时间复杂度较高。单调队列可以帮助我们优化状态转移的过程，将时间复杂度从 $O(n^2)$ 降低到 $O(n)$。

2. 示例问题：最大子数组和（带限制长度）

给定一个整数数组 $nums$ 和一个整数 $k$，求长度不超过 $k$ 的连续子数组的最大和。

算法思路

我们可以使用动态规划来解决这个问题。定义 $dp[i]$ 表示以第 $i$ 个元素结尾的长度不超过 $k$ 的连续子数组的最大和。状态转移方程为：

$[dp[i]={\max }_{j=\max (0,i-k)}^{i-1}(dp[j])+nums[i]]$

为了优化状态转移的过程，我们可以使用单调队列来维护 $dp[j]$ 的最大值。

代码实现（Java）

import java.util.ArrayDeque;
import java.util.Deque;public class MaxSubarraySumWithLimit {public int maxSubarraySum(int[] nums, int k) {int n = nums.length;int[] dp = new int[n];dp[0] = nums[0];int maxSum = dp[0];Deque<Integer> deque = new ArrayDeque<>();deque.offerLast(0);for (int i = 1; i < n; i++) {// 移除不在窗口内的元素if (!deque.isEmpty() && i - deque.peekFirst() > k) {deque.pollFirst();}dp[i] = (deque.isEmpty() ? 0 : dp[deque.peekFirst()]) + nums[i];// 维护单调递减队列while (!deque.isEmpty() && dp[deque.peekLast()] <= dp[i]) {deque.pollLast();}deque.offerLast(i);maxSum = Math.max(maxSum, dp[i]);}return maxSum;}public static void main(String[] args) {MaxSubarraySumWithLimit solution = new MaxSubarraySumWithLimit();int[] nums = {1, -2, 3, -4, 5, -6};int k = 3;System.out.println(solution.maxSubarraySum(nums, k));}
}

总结
单调队列作为一种高效的数据结构，不仅在滑动窗口问题中表现出色，在图论和动态规划等复杂场景中也能发挥重要作用。通过维护队列的单调性，我们可以在动态更新数据的过程中，快速找到局部最值，从而优化算法的时间复杂度。

That’s all, thanks for reading~~
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～