个人觉得虽然单调栈和单调队列都单调，但是用法和适用的问题却大相径庭。

单调队列

单调队列是指一个队列内部元素具有单调性的数据结构，分为单调递增队列和单调递减队列。

单调队列满足三个性质：

  • 单调队列也是队列，满足先进先出
  • 单调队列必须满足从队头到队尾的单调性
  • 排在队列前面的元素比排在队列后面的元素要先进队

假设一个队列 <– 0 1 3 1 2 5 <–，简单的理解的话 1 2 这一段对于整个队列的最大值是没有影响的，因为 1 2 先出队，且出队的时候最大值不会变，还是 5 ，所以 1 2 可以直接去掉。

对于单调递增队列，对于一个元素如果它大于等于队尾元素， 那么直接把元素进队， 如果这个元素小于队尾元素，则将队尾元素出队列，直到满足这个元素大于等于队尾元素。

对于单调递减队列，对于一个元素如果它小于等于队尾元素， 那么直接把元素进队， 如果这个元素大于队尾元素，则将队尾元素出队列，直到满足这个元素小于等于队尾元素。

这里我没有强调严格的单调性，因为我认为不递减或不递增是可行的，这个问题要因题目而异。大多数严格的情况下，不加等号的情况下需要保留下标；不是严格的话数据会有冗余，这个要自己取舍~~

实现的话推荐双端队列实现。单调队列应用：

  • 均摊 O(1) 的可以获得最大值的队列
  • 优化 DP
  • 给定一个数列，求长度为 m 的子串（滑动窗口）的最大值或最小值
  • 查询区间最大值或者最小值

单调栈

单调栈是指一个栈内部元素具有单调性的数据结构，分为单调递增栈和单调递减栈。

单调栈满足三个性质：

  • 单调栈也是栈，满足先进后出。
  • 单调栈必须满足从栈顶到栈底的单调性
  • 排在栈越下面的元素比排在栈上面的元素要先进栈

栈的实现和队列一模一样，插入模式一样，只有弹出方式不一样。

对于单调递增栈（从栈底到栈顶单调递增），应用：

  • 对于一个元素
    • 求左边第一个比它小的数
    • 求左边第一个比它大的数
    • 求右边第一个比他小的数
    • 这些数的距离
  • 最长的单调区间
  • 某个数为最值的最长区间

此外，当访问到第 i 个元素时，单调栈维护的区间为 [0, i) ，而单调队列维护的区间为 (last_pop, i)。

单调队列题目

Leetcode 面试题59 - II 队列的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class MaxQueue
{
public:
	// MaxQueue() {}

	int max_value()
	{
		if (deq.empty() || que.empty()) return -1;

		return deq.front();
	}

	void push_back(int value)
	{
		que.push(value);
		
		while ((!deq.empty()) && value > deq.back()) deq.pop_back();
		deq.push_back(value);
	}

	int pop_front()
	{
		if (deq.empty() || que.empty()) return -1;

		const auto now = que.front();
		que.pop();
		if (now == deq.front()) deq.pop_front();
		return now;
	}

private:
	queue<int> que;
	deque<int> deq;
};

/**
 * Your MaxQueue object will be instantiated and called as such:
 * MaxQueue* obj = new MaxQueue();
 * int param_1 = obj->max_value();
 * obj->push_back(value);
 * int param_3 = obj->pop_front();
 */

Leetcode 239 滑动窗口最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution
{
public:
	inline void add(deque<int>& deq, int num)
	{
		while ((!deq.empty()) && (num > deq.back())) deq.pop_back();

		deq.push_back(num);
	}

	vector<int> maxSlidingWindow(vector<int>& nums, int k)
	{
		if (k == 0) return {};

		vector<int> ans;

		deque<int> deq;
		for (auto i = 0; i < k; i++) add(deq, nums[i]);
		ans.emplace_back(deq.front());
		auto now = k;

		while (now < nums.size())
		{
			if (deq.front() == nums[now - k]) deq.pop_front();
			add(deq, nums[now]);
			ans.emplace_back(deq.front());
			now++;
		}

		return ans;
	}
};

单调栈题目

Leetcode 84 柱状图中最大的矩形

目标：对于每一个元素找到左右第一个比他小的元素

当元素一个出栈时，进行比较的新元素是这个元素右边第一个比他小的元素

当元素一个出栈后，新的栈顶元素是这个元素左边第一个比他小的元素

还有，前面和后面记得塞一个0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution
{
public:
	int largestRectangleArea(vector<int>& heights)
	{
		vector<int> h(heights.size() + 2, 0);
		copy(heights.begin(), heights.end(), h.begin() + 1);

		auto ans = 0;
		stack<int> s;

		for (auto i = 0; i < h.size(); i++)
		{
			while ((!s.empty()) && (h[i] < h[s.top()]))
			{
				const auto now = h[s.top()];
				s.pop();
				const auto L = s.top(), R = i;
				ans = max(ans, now * (R - L - 1));
			}
			s.push(i);
		}

		return ans;
	}
};