队列

###普通队列queue

模拟队列

可以用一个数组+一个头指针+一个尾指针模拟队列：

const int N = 1e5 + 7;

int que[N], hh, tt = -1; // hh => head指针，指向队头; tt => tail指针，指向队尾
						 // 注意tt初始化为-1，ss与tt重合时也表示有元素

que[++ tt] = x;          // push

hh ++;                   // pop

que[hh];                 // top

if (tt >= hh)            // not empty
else                     //empty

###双端队列deque

单调队列

滑动窗口最值

洛谷-P1886.滑动窗口

子区间长度不超过 k 的最大子区间和

(https://www.acwing.com/problem/content/137/)

#include <deque>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 3e5 + 7;
const int INF = 0x3f3f3f3f;

int n, m;
vector<int> arr(N, 0);
vector<LL> sum(N, 0);

int main() {
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &arr[i]);
    }
    for (int i = 1; i <= n; i ++) {
        sum[i] = sum[i - 1] + arr[i];
    }
    
    LL res = -INF;
    deque<int> Q;
    Q.push_back(0); // 插入sum[0]
    for (int i = 1; i <= n; i ++) {
        while (!Q.empty() && i - Q.front() + 1 > m + 1) {
            Q.pop_front();
        }
        
        res = max(res, sum[i] - sum[Q.front()]);
        
        while(!Q.empty() && sum[Q.back()] >= sum[i]) {
            Q.pop_back();
        }
        Q.push_back(i);
    }
    
    cout << res << endl;
    
    return 0;
}

luogu-[USACO11OPEN].Mowing the Lawn

这道题和上面那道最大K子序和非常像

子数组和至少为 k 的最短非空子数组长度

https://leetcode-cn.com/problems/shortest-subarray-with-sum-at-least-k/