本文共 2256 字，大约阅读时间需要 7 分钟。

题目链接:

题目描述

给定一个大小为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

解题思路

题意:给你一个长度为n的序列，长度为k的窗口在上面向右移动，求出每次移动时窗口内数字的最小值和最大值。

Accepted Code:

/*  * @Author: lzyws739307453  * @Language: C++  */#include 
   
    using namespace std;const int MAXN = 1000005;struct Queue {    int data[MAXN];    int front_, rear;    Queue() {        front_ = 0, rear = -1;    }    void push(int x) {        data[++rear] = x;    }    void pop_front() {        front_++;    }    void pop_back() {        rear--;    }    int front() {        return data[front_];    }    int back() {        return data[rear];    }    int size() {        return rear - front_ + 1;    }    bool empty() {        return rear < front_;    }}Qmin, Qmax;int cnt_max = 0, cnt_min = 0;int spt[MAXN], res_max[MAXN], res_min[MAXN];int main() {    int n, m;    scanf("%d%d", &n, &m);    for (int i = 1; i <= n; i++)        scanf("%d", &spt[i]);    for (int i = 1; i <= n; i++) {        while (!Qmax.empty() && Qmax.front() + m - 1 < i)            Qmax.pop_front();        while (!Qmin.empty() && Qmin.front() + m - 1 < i)            Qmin.pop_front();        while (!Qmax.empty() && spt[Qmax.back()] <= spt[i])            Qmax.pop_back();        while (!Qmin.empty() && spt[Qmin.back()] >= spt[i])            Qmin.pop_back();        Qmax.push(i), Qmin.push(i);        res_max[++cnt_max] = Qmax.front();        res_min[++cnt_min] = Qmin.front();    }    for (int i = m; i <= n; i++)        printf("%d%c", spt[res_min[i]], "\n "[i != n]);    for (int i = m; i <= n; i++)        printf("%d%c", spt[res_max[i]], "\n "[i != n]);    return 0;}
   

转载地址：https://lzyws739307453.blog.csdn.net/article/details/99974192 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！