YuriCode
0%

队列

发表于 更新于 分类于
本文字数： 4k 阅读时长 ≈ 4 分钟

队列

队列（Queue） 是一种常见的线性数据结构，具有先进先出（FIFO, First In First Out）的特点。它类似于现实生活中的排队场景：最先加入队列的元素最先被处理。

用数组模拟队列

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
43
44
45
46
47
48
49
#include <iostream>
using namespace std;

const int N = 100010;

int q[N], hh = 0, tt = -1;

void push(int x)
{
	q[++tt] = x;
}

void pop()
{
	hh++;
}

void empty()
{
	if (tt >= hh) cout << "NO" << endl;
	else cout << "YES" << endl;
}

void query()
{
	cout << q[hh] << endl;
}

int main()
{
	int M;
	cin >> M;
	while (M--) {
		string op;
		cin >> op;
		if (op == "push") {
			int x; cin >> x;
			push(x);
		} else if (op == "pop") {
			pop();
		} else if (op == "empty") {
			empty();
		} else {
			query();
		}
	}
	
	return 0;
}

单调队列

左程云版

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve() {
    // 单调队列
    // 得到滑动窗口中的最大值和最小值

    // 维护最大值
    // 头 -> 尾 
    // 大 -> 小 (严格)
    // 从右边加数字
    // 如果有一个数push_back后不符合条件，那么就push_pop直到满足条件
    // 滑动窗口的最大值就是队头
    // 从左边减数字
    // 如果当前队头的下标为过期下标，那么pop_front
}

acwing版

https://www.acwing.com/problem/content/156/

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
43
44
45
46
#include <iostream>

using namespace std;

const int N = 1000010;

int a[N], q[N];

int main()
{
	//此处使用双端队列
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> a[i];
	//队尾插入，队头获取
	int hh = 0, tt = -1;
	//找到窗口最小值
	//此处队列模拟的是下标
	for (int i = 0; i < n; i++) {
		//因为窗口中最多只能容纳k个元素
		//i - k + 1所对应的就是窗口最左边的下标（合法的）
		//如果队头比合法的最左边下标还要小，那么就说明元素多了
		//通过h++，移除队头元素
		if (hh <= tt && i - k + 1 > q[hh]) hh++;
		//此处循环的作用就是把当前元素的前面所有元素进行一一对比
		//如果前面的元素比较大，那么就把这个元素移除
		//这里通过tt--，是从队尾进行元素移除
		while (hh <= tt && a[i] <= a[q[tt]]) tt--;
		q[++tt] = i;
		//窗口最左边的下标要>=0的时候才会输出值
		if (i - k + 1 >= 0) cout << a[q[hh]] << " ";
	}
	cout << endl;
	//找到窗口的最大值
	hh = 0, tt = -1;
	for (int i = 0; i < n; i++) {
		if (hh <= tt && i - k + 1 > q[hh]) hh++;
		//找到比当前元素小的就删除
		while (hh <= tt && a[i] >= a[q[tt]]) tt--;
		q[++tt] = i;
		if (i - k + 1 >= 0) cout << a[q[hh]] << " ";
	}
	
	return 0;
}

习题

滑动窗口的最大值

https://leetcode.cn/problems/sliding-window-maximum/

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
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& arr, int k) {
        int n = arr.size();
        vector<int> ans;
        deque<int> dq;

        // 先处理前 k 个元素，初始化窗口
        for (int i = 0; i < k; i++) {
            while (!dq.empty() && arr[i] >= arr[dq.back()]) dq.pop_back();
            dq.push_back(i);
        }
        ans.push_back(arr[dq.front()]); 

        // 滑动窗口
        for (int r = k; r < n; r++) {
            int l = r - k + 1; 

            // 维护队列：移除窗口外的元素
            while (!dq.empty() && dq.front() < l) dq.pop_front();

            // 维护队列：保持单调性
            while (!dq.empty() && arr[r] >= arr[dq.back()]) dq.pop_back();
            dq.push_back(r);

            // 记录当前窗口的最大值
            ans.push_back(arr[dq.front()]);
        }
        return ans;
    }
};

绝对差不超过限制的最长连续子数组

https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

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
43
44
45
46
47
48
49
class Solution {
public:
    int longestSubarray(vector<int>& arr, int limit) {
        // 如果子数组内的最大值 - 最小值 <= limit
        // 那么这样的子数组就满足条件
        // 求出最长的连续子数组长度

        // 对于一个滑动窗口而言，如果增加一个数
        // 那么窗口内的最大值只可能 ↑ 或不变
        // 最小值只可能 ↓ 或不变
        // 同理如果减去一个数最大值只可能 ↓ 或不变
        // 最小值只可能 ↑ 或不变

        // 如果一个窗口已经符合了条件，即abs(max - min) <= limit
        // 如果缩小窗口一定成立，所以窗口只能通过增大来判定最大的符合条件的子数组
        // 同理如果当前窗口已经不达标，再增加肯定也不达标
        // 看数加进来之后会不会符合条件
        // 如果不符合条件，删除队列中不符合的， l++ 继续判断
        deque<int> maxDeque;
        deque<int> minDeque;
        int ans = 0;
        int n = arr.size();
        for (int r = 0, l = 0; r < n; r++) {
            // 维护最大值队列（大 -> 小）
            while (!maxDeque.empty() && arr[r] >= arr[maxDeque.back()]) {
                maxDeque.pop_back();
            }
            maxDeque.push_back(r);

            // 维护最小值队列（小 -> 大）
            while (!minDeque.empty() && arr[r] <= arr[minDeque.back()]) { 
                minDeque.pop_back();
            }
            minDeque.push_back(r);

            while (!maxDeque.empty() && !minDeque.empty() && arr[maxDeque.front()] - arr[minDeque.front()] > limit) {
                // 如果加进来的数是最大导致的，那就删除
                if (maxDeque.front() == l)
                    maxDeque.pop_front(); 
                // 如果加进来的数是最小导致的。也要删除
                if (minDeque.front() == l)
                    minDeque.pop_front(); 
                l++;
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};