xindoo is
always here

poj 2823 Sliding Window


      在这里先说一道微软的面试题目———《队列中的最大值》

      让你设计一个队列,是其求里面最大值的时间复杂度尽可能的低,但这个队列除了最大值外,就是一个普通的队列,该怎么进出还是怎么进出,并不是优先队列。

      对于一堆树,我们求其中最大值一般都会直接遍历一次,然后找到最大值,这样的话时间复杂度是O(n),如果在这道题里面用这种方法总的时间复杂度会到O(n^2),考虑到n的大小,这种方法显然是行不通的。有没有更为快速,可能有人想到使用堆,这也是优先队列使用的方法,如果实现的好的话,可以把时间复杂度从O(n)降到O(logn),不过,我这里说的不是这种方法,我要来说一下时间复杂度为O(1)的一种算法。

      在说这个算法之前,我先要讲两个东西———栈里面的最大值和用两个栈实现一个队列。

      我们很容易可以把求栈里面的最大值问题的时间复杂度降到O(1),我们在栈的每一个节点保存两个值Val和Max,一个是原来应该保存的值,另一个是max值,就是当这个节点是栈顶时栈中最大的值,如果新来一个数x,那么添加一个节点val = x, Max = max(stack.top().Max, x),这样的话即使我们执行了多长pop操作也可以在O(1)的时间里求出里面的最大值,如果不明白请看下图。

比如说这就是一个有7个元素的栈,左边val就是原来的值,右边就是max,比如说当top指针如图所示,5就是栈里面最大的值,如果我们执行一次pop,我们还是可以一次得到栈里面最大的值。

        关于用两个栈实现一个队列,如果将一串数分别入栈和入队列,然后出栈出队列,我们就会发现一个顺序反了,一个没有。如果我们用栈实现队列必须用两个栈,反一次,然后再反一次,不就正好是队列的顺序了吗?

        然后我们姑且就称这个用栈实现的队列叫Queue吧,这样的话还有一个出人对列的问题,还记得出队列的顺序吗?先入的先出,那我们到底应该怎么实现呢? 看看这个Queue里面吧, 里面有个两个栈,我们就叫In和Out栈吧。如下图

    为什么是In和Out,因为,我们入Queue的时候把元素放的In栈里面,出Queue的时候从Out栈里面出,还有在出入Queue的时候适时把In里面的元素放到Out里面,适时到底是什么时候?  就是出Queue的时候Out里面没有元素了,然后把In里面所有元素压的Out栈里面,注意是所有元素,这样才能保证他们出入Queue的顺序正好是一个出入队列的顺序。

         说了这么多,我们在来看看这道题,一个区间每次向后移动一位,然后求里面的最大最小值,这个过程不就是先把最早进入区间的一个数去掉,然后加入一个数,这个不就是一个队列吗??然后让你找队列里面的最大最小值(详情请参考《剑指offer》一书,具体多少页我忘记了)  有了上面两个知识,我们就可以在O(n)的时间复杂度里面解决这个问题了。

         下面是解题代码,不过还是超时了,我想可能是因为多次调用函数的原因,思路是完全正确的,大家可以尝试把那些东西写一起,还有这个题的输入输出数据量极大,不要用cin cout输入输出,不然会超时的。

备注:这道题貌似可以用动态规划的方法做,不过本弱菜不会,如有读者会希望不吝赐教。

//poj 2823
//2013-08-03-10.39
#include <stdio.h>
#include <stack>
#include <algorithm>
#define maxn 1000006
using namespace std;

int maxv[maxn];
int minv[maxn];
int cnt;

struct node
{
    int val, maxv, minv;
};
stack<node> sin;
stack<node> sout;

void push(int v)
{
    if (sin.empty())
    {
        node tmp;
        tmp.val = v;
        tmp.maxv = v;
        tmp.minv = v;
        sin.push(tmp);
    }
    else
    {
        node tmp = sin.top();
        tmp.val = v;
        tmp.maxv = max(tmp.maxv, v);
        tmp.minv = min(tmp.minv, v);
        sin.push(tmp);
    }
}

void pop()
{
    if (sout.empty())
    {
        while (!sin.empty())
        {
            node tmp = sin.top();
            sin.pop();
            if (sout.empty())
            {
                tmp.maxv = tmp.val;
                tmp.minv = tmp.val;
                sout.push(tmp);
            }
            else
            {
                node tmp2 = sout.top();
                tmp.maxv = max(tmp2.maxv, tmp.val);
                tmp.minv = min(tmp2.minv, tmp.val);
                sout.push(tmp);
            }
        }
        sout.pop();
    }
    else
    {
        sout.pop();
    }
}

void getval()
{
    if(!sin.empty() && !sout.empty())
    {
        node tin = sin.top(), tout = sout.top();
        minv[cnt] = min(tin.minv, tout.minv);
        maxv[cnt] = max(tin.maxv, tout.maxv);
        cnt++;
    }
    if (sin.empty() && !sout.empty())
    {
        node tout = sout.top();
        minv[cnt] = tout.minv;
        maxv[cnt] = tout.maxv;
        cnt++;
    }
    if (!sin.empty() && sout.empty())
    {
        node tin = sin.top();
        minv[cnt] = tin.minv;
        maxv[cnt] = tin.maxv;
        cnt++;
    }
}

int main()
{
    int n, k;
    while (scanf("%d %d", &n, &k) != EOF)
    {
        int tmp;
        cnt = 1;
        while (!sin.empty())
            sin.pop();
        while (!sout.empty())
            sout.pop();
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &tmp);
            push(tmp);
            if (i == k)
            {
                getval();
            }
            if (i > k)
            {
                pop();
                getval();
            }
        }
        for (int i = 1; i < cnt; i++)
        {
            if (i == 1)
                printf("%d", minv[i]);
            else
                printf(" %d", minv[i]);
        }
        puts("");
        for (int i = 1; i < cnt; i++)
        {
            if (i == 1)
                printf("%d", maxv[i]);
            else
                printf(" %d", maxv[i]);
        }
        puts("");
    }
    return 0;
}


 

打赏
未经允许不得转载:XINDOO » poj 2823 Sliding Window
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏