您现在的位置是:首页 >其他 >数据结构与算法(十一) 单调栈与单调队列网站首页其他
数据结构与算法(十一) 单调栈与单调队列
大家好,我是半虹,这篇文章讲单调栈和单调队列
1 单调栈
栈是一种很常见的数据结构,具有后进先出的特点
而单调栈则是一种特殊的栈,在进栈出栈时,通过某些操作使栈内元素保持单调性
在这里,栈内元素的单调性是指元素单调递增或者单调递减
单调栈的应用场景并不多,最典型的莫过于下一个更大元素,更小元素同理可求
简单来说就是对于数组中的每个元素,找到下一个比自己大的元素及其所在位置
举个例子,给定数组 [2, 3, 1, 5, 4]
,位置从 0
开始算
- 对于元素
2
,下一个更大元素是3
,其所在位置是1
- 对于元素
3
,下一个更大元素是5
,其所在位置是3
- 对于元素
1
,下一个更大元素是5
,其所在位置是3
- 对于元素
5
,下一个更大元素不存在/
- 对于元素
4
,下一个更大元素不存在/
使用单调栈怎么解决呢?我们只需要去反向遍历一次数组,并将元素依次进栈
同时在每个元素进栈前,先将栈内小于等于它的元素出栈,此时栈顶元素即为下一个更大元素
在整个进栈出栈过程中,栈内元素始终保持单调递增状态,所以被称为单调栈
当前元素 | 当前元素入栈前 栈状态 | 更小元素出栈后 栈状态 | 下一个更大元素 | 当前元素入栈后 栈状态 |
---|---|---|---|---|
4 | [] | [] | / | [4] |
5 | [4] | [] | / | [5] |
1 | [5] | [5] | 5 | [5, 1] |
3 | [5, 1] | [5] | 5 | [5, 3] |
2 | [5, 3] | [5, 3] | 3 | [5, 3, 2] |
对应代码如下:
vector<int> nextGreaterElement(vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return {};
}
vector<int> r(n);
stack <int> s;
// 反向遍历
for (int i = n - 1; i >= 0; i--) {
// 更小元素出栈
while (!s.empty() && s.top() <= nums[i]) s.pop();
// 下一更大元素
r[i] = !s.empty() ? s.top() : -1;
// 当前元素入栈
s.push(nums[i]);
}
return r;
}
相关例题如下:
- 下一个更大元素 I | leetcode496
给定数组 nums1
和 nums2
,求 nums1
中每个元素的下一个更大元素
nums1
中元素 x
的下一个更大元素是指 x
在 nums2
中对应位置右侧第一个比 x
大的元素
先用单调栈求
nums2
中每个元素的下一个更大元素再用哈希表存
nums2
中每个元素与下一个更大元素的对应关系最后遍历一次
nums1
在哈希表中找下一个更大元素
class Solution {
public:
vector<int> nextGreaterElement( vector<int>& nums1, vector<int>& nums2 ) {
vector<int> nextG = myNextGreaterElement(nums2);
unordered_map<int, int> map;
for (int i = 0; i < nums2.size(); i++) {
map[nums2[i]] = nextG[i];
}
vector<int> ans(nums1.size());
for (int i = 0; i < nums1.size(); i++) {
ans[i] = map[nums1[i]];
}
return ans;
}
// 模板
vector<int> myNextGreaterElement(vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return {};
}
vector<int> r(n);
stack <int> s;
for (int i = n - 1; i >= 0; i--) {
while (!s.empty() && s.top() <= nums[i]) s.pop();
r[i] = !s.empty() ? s.top() : -1;
s.push(nums[i]);
}
return r;
}
};
- 下一个更大元素 II | leetcode503
给定数组 nums
,求数组中每个元素的下一个更大元素,但该数组是循环数组
处理循环数组最简单的方法,就是复制一份数组拼到后面,然后其他的操作和之前一样
但是在实现时,我们无需真正复制一份数组,而是可以通过修改遍历方式模拟这个过程
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return {};
}
vector<int> r(n);
stack <int> s;
// 起始从 n - 1 变成 n * 2 - 1
for (int i = n * 2 - 1; i >= 0; i--) {
// 取值从 i 变成 i % n
while (!s.empty() && s.top() <= nums[i % n]) s.pop();
r[i % n] = !s.empty() ? s.top() : -1;
s.push(nums[i % n]);
}
return r;
}
};
- 每日温度 | leetcode739
给定数组 nums
,求数组中每个元素的下一个更大元素与当前元素之间的距离
还是用单调栈,但栈内保存的是索引而非值
然后在出栈时,计算当前元素与下一个更大元素之间的距离
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return {};
}
vector<int> r(n);
stack <int> s;
for (int i = n - 1; i >= 0; i--) {
// 栈保存索引
// 入栈时计算下一个更大元素和当前元素相差的距离
while (!s.empty() && nums[s.top()] <= nums[i]) s.pop();
r[i] = !s.empty() ? s.top() - i : 0;
s.push(i);
}
return r;
}
};
2 单调队列
队列也是很常见的数据结构,具有先进先出的特点
单调队列是一种特殊的队列,在进队出队时,通过某些操作使队内元素保持单调性
在这里,队内元素的单调性是指元素单调递增或者单调递减
单调队列的应用场景很少,其通常会配合滑动窗口一起使用来求解滑动窗口最大值
一道典型的例题如下所示:leetcode239
给定整数数组 nums
,给定窗口大小 k
,窗口从数组最左侧滑动到数组最右侧,求窗口每次移动最大值
输入:nums = [4, 5, 3, 2, 1, 4, 3, 2],k = 3;输出:[3, 3, 5, 5, 6, 7]
解释:
滑动窗口的位置 当前窗口最大值
[4 5 3] 2 1 4 3 2 5
4 [5 3 2] 1 4 3 2 5
4 5 [3 2 1] 4 3 2 3
4 5 3 [2 1 4] 3 2 4
4 5 3 2 [1 4 3] 2 4
4 5 3 2 1 [4 3 2] 4
解题的关键是当窗口移动时,如何维护窗口的最大值,这里就要用到单调队列,具体步骤如下:
- 初始阶段,步骤
1 ~ k
:窗口左端保持不变,窗口右端右移一步 - 更新阶段,步骤
k ~ n
:窗口左端右移一步,窗口右端右移一步
窗口左端右移,意味着旧窗口左端元素出队,如果该元素已不在队列,那么无事发生
窗口右端右移,意味着新窗口右端元素进队,注意该元素在进队之前,要先将队列中小于等于它的元素出队
在进队出队时,队内元素始终保持单调递增,所以这被称为单调队列,该队列具体用双端队列实现
步骤 | 当前元素 | 初始队列状态 | 出队元素 | 出队后队列状态 | 进队元素 | 进队后队列状态 | 最大 |
---|---|---|---|---|---|---|---|
1 | 4 | [] | / | [] | 4 | [4] | / |
2 | 5 | [4] | / | [4] | 5 | [5] | / |
3 (k ) | 3 | [5] | / | [5] | 3 | [5, 3] | 5 |
4 | 2 | [5, 3] | 4 | [5, 3] | 2 | [5, 3, 2] | 5 |
5 | 1 | [5, 3, 2] | 5 | [3, 2] | 1 | [3, 2, 1] | 3 |
6 | 4 | [3, 2, 1] | 3 | [2, 1] | 4 | [4] | 4 |
7 | 3 | [4] | 2 | [4] | 3 | [4, 3] | 4 |
8 (n ) | 2 | [4, 3] | 1 | [4, 3] | 2 | [4, 3, 2] | 4 |
对应代码如下:
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
if (n == 0) {
return {};
}
vector<int> r;
deque <int> q;
// 初始阶段
for (int i = 0; i < k; i++) {
// 新窗口右端元素进队
while (!q.empty() && nums[q.back()] <= nums[i]) {
q.pop_back();
}
q.push_back(i);
}
r.push_back(nums[q.front()]); // 保存结果
// 更新阶段
for (int i = k; i < n; i++) {
// 旧窗口左端元素出队
while (!q.empty() && q.front() <= i - k) {
q.pop_front();
}
// 新窗口右端元素进队
while (!q.empty() && nums[q.back()] <= nums[i]) {
q.pop_back();
}
q.push_back(i);
r.push_back(nums[q.front()]); // 保存结果
}
// 返回结果
return r;
}
};
好啦,本文到此结束,感谢您的阅读!
如果你觉得这篇文章有需要修改完善的地方,欢迎在评论区留下你宝贵的意见或者建议
如果你觉得这篇文章还不错的话,欢迎点赞、收藏、关注,你的支持是对我最大的鼓励 (/ω\)