滑动窗口

滑动窗口

https://ac.nowcoder.com/acm/problem/50528

这题滑动窗口,首先我那道题,发现是个区间最大值和最小值。很显然,可以用线段树和树状数组或者ST表去强行区间查询。

很不幸,牛客把内存卡的死死的,因为这题我在POJ 2823上做过,那里内存不严格,所以我线段树一发就过了。

这里线段树只能拿70f分。

滑动窗口是个经典的单调队列的题目,本题要求最大值和最小值,是维护2个单调队列,一个单调递减队列,队列头是保证对大值,一个是单调递增队列,保证队头最小值。

那么,我们如何去维护他呢??

这里我们以单调递减队列为例。

首先我们要知道,每次算区间的时候,整个区间k相当于移动了一格。那么我们没必要重新去计算。 我们每次去计算的时候,先判断下,队列顶的元素是不是超出我们的区间范围了,如果超出了,那么pop掉,因为超出区间范围,我们没必要算他了。如果当前元素大于队列顶部的那个元素,我们需要把队列顶部的那个元素弹出,因为后面最大值将不会是他了。判断好上面的情况后,我们需要把这个元素加到队列尾部,但是加的时候,我们需要去判断当前元素是不是大于尾部元素,如果大于尾部元素,也pop掉。我们实时维护的是队头最大值,这点要牢记。 这是最大值的做法,最小值也雷同,只要改变大于符号为小于符号即可。

题解大佬用了数组来模拟,我是用双端队列deque来模拟的。

#include <bits/stdc++.h>

using namespace std;

const int N=1e6+100;

int n,k;

struct Node
{
    int val;
    int pos;
}a[N];

deque<Node>dq;//计算最大值
deque<Node>dq2;//计算最小值 
int x[N];
int y[N];

void solve()
{
    for(int i=1;i<=n;i++)
    {
        if(dq.empty())
        {//如果是空的,直接加入 
            dq.push_back(a[i]); 
        }
        else
        {
            Node top=dq.front();//访问头结点
            if(i-top.pos>=k)
            {
                dq.pop_front();
            }//如果超出区间直接删掉
            if(a[i].val>dq.front().val)
            {
                dq.pop_front();
            } 
            while(!dq.empty()&&a[i].val>dq.back().val)
            {
                dq.pop_back();
            }
            dq.push_back(a[i]); 
        } 
        x[i]=dq.front().val;
    }

    for(int i=1;i<=n;i++)
    {
        if(dq2.empty())
        {//如果是空的,直接加入 
            dq2.push_back(a[i]); 
        }
        else
        {
            Node top=dq2.front();//访问头结点
            if(i-top.pos>=k)
            {
                dq2.pop_front();
            }//如果超出区间直接删掉
            if(a[i].val<dq2.front().val)
            {
                dq2.pop_front();
            } 
            while(!dq2.empty()&&a[i].val<dq2.back().val)
            {
                dq2.pop_back();
            }
            dq2.push_back(a[i]); 
        } 
        y[i]=dq2.front().val;
    }
}

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

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

    solve();

    for(int i=k;i<=n;i++)
    {
        printf("%d%c",y[i],i==n?'\n':' '); 
    }

    for(int i=k;i<=n;i++)
    {
        printf("%d%c",x[i],i==n?'\n':' '); 
    } 
    return 0;
}
全部评论

相关推荐

05-11 11:48
河南大学 Java
程序员牛肉:我是26届的双非。目前有两段实习经历,大三上去的美团,现在来字节了,做的是国际电商的营销业务。希望我的经历对你有用。 1.好好做你的CSDN,最好是直接转微信公众号。因为这本质上是一个很好的展示自己技术热情的证据。我当时也是烂大街项目(网盘+鱼皮的一个项目)+零实习去面试美团,但是当时我的CSDN阅读量超百万,微信公众号阅读量40万。面试的时候面试官就告诉我说觉得我对技术挺有激情的。可以看看我主页的美团面试面经。 因此花点时间好好做这个知识分享,最好是单拉出来搞一个板块。各大公司都极其看中知识落地的能力。 可以看看我的简历对于博客的描述。这个帖子里面有:https://www.nowcoder.com/discuss/745348200596324352?sourceSSR=users 2.实习经历有一些东西删除了,目前看来你的产出其实很少。有些内容其实很扯淡,最好不要保留。有一些点你可能觉得很牛逼,但是面试官眼里是减分的。 你还能负责数据库表的设计?这个公司得垃圾成啥样子,才能让一个实习生介入数据库表的设计,不要写这种东西。 一个公司的财务审批系统应该是很稳定的吧?为什么你去了才有RBAC权限设计?那这个公司之前是怎么处理权限分离的?这些东西看着都有点扯淡了。 还有就是使用Redis实现轻量级的消息队列?那为什么这一块不使用专业的MQ呢?为什么要使用redis,这些一定要清楚, 就目前看来,其实你的这个实习技术还不错。不要太焦虑。就是有一些内容有点虚了。可以考虑从PR中再投一点产出
点赞 评论 收藏
分享
喜欢核冬天的哈基米很想上市:会爆NullPointerException的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务