当前位置：首页 > news >正文

单调队列深度解析(下)

news 2025/7/20 8:48:43

单调队列深度解析-下

- 一、单调队列在图论中的应用
- - 1. 问题背景
  - 2. 示例问题：最短路径上的最大边权
  - - 算法思路
    - 代码实现（Python）
- 二、单调队列在动态规划中的应用
- - 1. 问题背景
  - 2. 示例问题：最大子数组和（带限制长度）
  - - 算法思路
    - 代码实现（Java）

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

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

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. 示例问题：最大子数组和（带限制长度）

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

算法思路

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

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

为了优化状态转移的过程，我们可以使用单调队列来维护 $d p [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));}
}