1.核心思想

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

2.问题特征

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

3. 分析流程

step1: 先利用普通栈(队列)给出解法
step2: 删除冗余的元素，得到具有单调性的栈和队列
写代码时候思考如何在栈顶或者队尾处理保持单调特性，然后特殊值在栈顶（底）、队头（尾）
step3: 优化枚举元素的O(n)的时间复杂度到O(1)

4. 代码模板

单调栈：
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()];
}

题目描述举例

给定一个长度为N的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出-1。
输入格式

第一行包含整数N，表示数列长度。

第二行包含N个整数，表示整数数列。
输出格式

共一行，包含N个整数，其中第i个数表示第i个数的左边第一个比它小的数，如果不存在则输出-1。
数据范围

1≤N≤105

1≤数列中元素≤109

样例

输入样例：
5
3 4 2 7 5

输出样例：
-1 3 -1 2 2

C 代码

#include<stdlib.h>
#include<stdio.h>

#define N 100010
#define bool char
#define true 1
#define false 0

int a[N], stk[N];
int cnt;
int n;

void push_back(int x);
void pop_back();
int  get_front();
bool is_empty();

int main()
{
    scanf("%d", &n);

    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }

    for(int i = 0; i < n; i++)
    {
        while(!is_empty() && a[get_front()] >= a[i]) pop_back();

        if(!is_empty()){
            printf("%d ", a[get_front()]);
            push_back(i);
        } else {
            printf("-1 ");
            push_back(i);
        }
    }
    return 0;
}

void push_back(int x)
{
    stk[cnt++] = x;
}

void pop_back()
{
    cnt--;
}

int  get_front()
{
    return stk[cnt - 1];
}

bool is_empty()
{
    return cnt == 0 ? true : false;
}

题目描述举例

给定一个大小为n≤106

的数组。

有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。

您只能在窗口中看到k个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为[1 3 -1 -3 5 3 6 7]，k为3。

您的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入格式

输入包含两行。

第一行包含两个整数n和k，分别代表数组长度和滑动窗口的长度。

第二行有n个整数，代表数组的具体数值。

同行数据之间用空格隔开。
输出格式

输出包含两个。

第一行输出，从左至右，每个位置滑动窗口中的最小值。

第二行输出，从左至右，每个位置滑动窗口中的最大值。

样例

输入样例：

8 3
1 3 -1 -3 5 3 6 7

输出样例：

-1 -3 -3 -3 3 3
3 3 5 5 6 7

C 代码

#include<stdlib.h>
#include<stdio.h>

#define N 1000010
#define bool char
#define true 1
#define false 0

int queue[N], a[N];
int head = 0;
int tail = 0;
int n = 0;
int k = 0;

void push_back(int x);
void pop_tail();
void pop_head();
int get_tail();
int get_head();
bool is_empty();
void reset_queue();

int main()
{
    scanf("%d%d", &n, &k);

    for(int i = 0; i < n; i++)
    {
        scanf("%d", &a[i]);
    }

    for(int i = 0; i < n; i++)
    {
        while(!is_empty() && get_head() < (i - k + 1)) pop_head();

        while(!is_empty() && a[get_tail()] >= a[i]) pop_tail();
        push_back(i);

        if(i >= k - 1){
            printf("%d ", a[get_head()]);
        }
        /*
        for(int p = head; p < tail; p++){
            printf("%d ", a[queue[p]]);
        }
        printf("\n");
        */
    }


    reset_queue();
    printf("\n");
    for(int i = 0; i < n; i++)
    {
        while(!is_empty() && get_head() < (i - k + 1)) pop_head();

        while(!is_empty() && a[get_tail()] <= a[i]) pop_tail();
        push_back(i);

        if(i >= k - 1){
            printf("%d ", a[get_head()]);
        }
        /*
        for(int p = head; p < tail; p++){
            printf("%d ", a[queue[p]]);
        }
        printf("\n");
        */
    }

    return 0;
}

void push_back(int x)
{
    queue[tail++] = x;
}

void pop_tail()
{
    tail --;
}
void pop_head()
{
    head ++;
}
int get_tail()
{
    return queue[tail - 1];
}
int get_head()
{
    return queue[head];
}
bool is_empty()
{
    return head == tail ? true : false;
}
void reset_queue()
{
    head = 0;
    tail = 0;
    memset(queue, 0, sizeof(queue));
}