河北大学暑期程序设计训练每日知识分享-day27

每日分享——单调栈&单调队列

1.核心思想

利用栈和队列的单调性质，优化枚举区间内极值O(n)的时间复杂度到O(1)

2. 问题特征

(1)区间内的极值(最大值，最小值)
(2)找当前数左(右)边第一个比当前数大(小)的数

3. 分析流程

step1: 先利用普通栈(队列)给出解法
step2: 删除冗余的元素，得到具有单调性的栈和队列
step3: 优化枚举元素的O(n)的时间复杂度到O(1)

4. 代码模板

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
单调栈：
for(int i = 0, j = x; i < n; i++)
{
    //栈不空&&冗余元素性质
    while(!is_empty() && check(a[front()], a[i])) pop();

    //找到目标元素
    if(!is_empty()){
        xx
    } else {
        //空栈
    }

    //别忘了把元素加入栈中
    push(x);
}

单调队列:
for(int i = 0, j = x; i < n; i++)
{
    //判断队列头是否需要出队列
    while(!is_empty() && get_head() < i - k + 1) pop_head();

    //队列不空&&冗余元素性质
    while(!is_empty() && check(a[front()], a[i])) pop_back();

    //这里对比单调栈需要先把元素加入队列中
    push_back(x);

    //找出区间的极值
    printf a[get_head()];
}