单调队列及应用

单调队列

单调队列是一种优先队列，要求元素是可排序的，或传入比较器。单调队列继承队列的以下性质：

• 可从队尾插入元素。
• 可从队头弹出元素。
• 在队列中的所有元素里，队头元素一定是最早插入的。在队列中的所有元素里，队尾元素一定是最晚插入的。（FIFO）

单调队列有以下特殊性质：

• 一个元素插入队列后，即使没有手动弹出，也不一定存在于该队列。

var queue=new MonotoneQueue();
queue.Enqueue(a);
queue.Enqueue(b);
Debug.Assert(queue.Contains(a) || queue.Contains(a) == false);

单调队列是个很小众的数据结构。

应用与实现

单调队列的一个应用是LeetCode的一道题

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

Window position                Max
---------------               -----
[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

Note:
You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty array.

作为单调队列的初学者，我们直接看答案。

这里使用一个单调递减队列，队头是最大的元素，队尾（即队列入口）为最小的元素。

对[1, 3, -1]依次入队

这是算法的第一步，比较简单。在继续之前，回忆单调队列的定义：单调队列是一种优先队列，要求元素是可排序的，或传入比较器。从定义中发现，1、元素携带一个Priority属性，该属性用于排序；2、元素允许携带其他数据。

题目要求超过窗口的元素要删掉，所以单调队列还必须记录元素索引。于是使用一个类保存索引和排序用的Priority。

[DebuggerDisplay("Index={Index}, Value={Value}")]
struct Data
{
	public Data(int index, int value)
	{
		Index = index;
		Value = value;
	}
	public int Index { get; }
	public int Value { get; }
}

下面是完整解答。单调队列没有完全封装起来。队列会从两头增减元素，使用数组实现不好，因为从队头删除会导致元素移动，有O(n)复杂度。如果用两个指针，实现起来比较麻烦，所以我这里用链表实现。

public int[] MaxSlidingWindow(int[] nums, int k)
{
	if (nums.Length == 0)
		return new int[0];
	int[] result = new int[nums.Length - k + 1];
	//用链表实现单调队列，因为需要从两端移除元素。
	//设尾端为peek。
	//设该队列为单调递减队列，First为最大值，Last为最大值。
	var monotoneQueue = new LinkedList<Data>();

	//初始化单调队列，同时也是处理初始窗口
	for (int i = 0; i < k - 1; i++)
		Enqueue(monotoneQueue, new Data(i, nums[i]));

	for (int i = 0; i < result.Length; i++)
	{
		Enqueue(monotoneQueue, new Data(i + k - 1, nums[i + k - 1]));
		result[i] = monotoneQueue.First.Value.Value;

		Debug.Assert(monotoneQueue.First.Value.Index >= i);
		if (monotoneQueue.First.Value.Index == i)
			monotoneQueue.RemoveFirst();
	}

	return result;
}

/// <summary>
/// Add an item to monotonic decreasing queue. If the item is larger than <see cref="LinkedList{T}.Last"/>,
/// <see cref="LinkedList{T}.Last"/> will be removed.
/// </summary>
/// <param name="monotonicDecreasingQueue"></param>
/// <param name="item"></param>
void Enqueue(LinkedList<Data> monotonicDecreasingQueue, Data item)
{
	while (monotonicDecreasingQueue.Last?.Value.Value < item.Value)
		monotonicDecreasingQueue.RemoveLast();

	monotonicDecreasingQueue.AddLast(item);
}

[DebuggerDisplay("Index={Index}, Value={Value}")]
struct Data
{
	public Data(int index, int value)
	{
		Index = index;
		Value = value;
	}
	public int Index { get; }
	public int Value { get; }
}

下面是封装后的单调队列

public class MonotoneQueue<T> : IEnumerable<T>
{
	private readonly IComparer<T> comparer;
	private readonly LinkedList<T> list = new LinkedList<T>();

	/// <summary>
	/// 
	/// </summary>
	/// <param name="comparer">用comparer的方法来决定单调递增还是单调递减</param>
	public MonotoneQueue(IComparer<T> comparer)
	{
		this.comparer = comparer;
	}

	public void Enqueue(T item)
	{
		while (list.Count > 0 && comparer.Compare(list.Last.Value, item) > 0)
			list.RemoveLast();

		list.AddLast(item);
	}

	public void Dequeue()
	{
		list.RemoveFirst();
	}


	public T Head => list.First.Value;


	public IEnumerator<T> GetEnumerator()
	{
		return list.GetEnumerator();
	}

	IEnumerator IEnumerable.GetEnumerator()
	{
		return list.GetEnumerator();
	}
}

如何在MaxSlidingWindow()方法里使用MonotoneQueue类，作为课后习题留个大家。

• ENDLESSLETHE. 单调队列和单调栈详解. . 2017-12-14 [2019-09-10].
• . 239. Sliding Window Maximum. LeetCode. [2019-09-11].