时间限制:5000 ms
内存限制:65535 KB

描述

有一串整数在排队……

有N个整数,你有一个可以框住M个连续段整数的木框,现在你想知道,对于这个队列中任意的连续M个整数,最大和最小的整数是哪个?

例:(M大小的窗口向右滑动)

1 2 3 2 1   M=2
1 2    MAX 2  MIN 1
2 3    MAX 3  MIN 2
3 2    MAX 3  MIN 2
2 1    MAX 2  MIN 1

最后需要输出的是两行:

1 2 2 1
2 3 3 2

输入格式

第一行包含一个整数T,表示有T组测试数据; 以下每组测试数据格式: 第一行包含2个整数N,M表示有N个整数在排队,取连续M个整数。 第二行包含N个整数。 其中N不大于1,000,000,M不大于N。

输出格式

按照题目描述格式输出结果,第一行为MIN,第二行为MAX

问题来源

软件学院07级数据结构第二次测试

题解

很久不考虑算法问题了的说……当然也好久不写解题报告了。上面这题让我体会到久违了的思考的乐趣(i.e.我废掉好久了>_<)

最显然的解法是利用平衡树始终保持木框内M个数的有序状态,大体是O(NlogM)的复杂度。这个不用多说。

问题是:能否找到O(N)的解法?在读下去之前你可以好好想想。

我纠结了好久,终于……也没想出来- – 尽管想出很多优化,终究还是不能达到要求。网上搜了下,看到 CS大牛csdn 上有人给出了一个解法(你也可以在读完全文后再回头看这一段):

是可以到o(n);

编程之美上有一个类似的问题:”队列中取最大值操作问题”;
实际上窗口移动就相当于对队列做了一次出队与入队操作,所以lz这道题可以套用该解法;

书上是使用两个栈来模拟队列,假设为分别 A,B;

1) 当入队的时候,push A; 2)

当出队的时候

  1. 若B非空, pop B,
  2. 若B为空,则先将A中的元素依次 pop 并 push 到 B,再 pop B;

这样,就使用两个栈达到了队列的功能;

同时,对于单个栈,由于 pop, push 都是在栈顶进行的,所以每个栈都可以方便地维护自己的最大值与最小值在栈内的索引;
以最大值为例;
max_idx 保存栈内最大值的索引;
另使用一个跟栈的最大长度一样的数组 idx , idx[i] 表示栈的索引范围在0到i-1的元素中的最大值的索引为 idx[i] ;
  1. 当push的时候,比较栈顶元素与栈的已保存的最大值,
  2. 若栈顶元素大于已保存的最大值,那么 idx[top]=max_idx,max_idx=top;
  3. 若栈顶元素不大于已保存的最大值,那么 idx[top]=max_idx (书上是 idx[top]=-1);
  4. 当pop的时候, max_idx=idx[top] (书上是先比较 topmax_idx ,若 top==max_idx ,则 max_idx=idx[top] );

具体到这个题目; 可以使用两个长度为m的栈来模拟窗口;

  1. 将前m个元素依次push到栈A;
  2. 移动窗口就相当于分别进行 pop B 与 push A 操作;
  3. 窗口的最大值 == max[A.items[A.max_idx]),B.items[B.max_idx])]

由于每个元素最多进入两栈各一次; 所以总的复杂度是o(n)的;

这个解法的确可行,但描述仍不直观。为什么两个栈暧昧地眉来眼去一番,就在O(N)时间内把问题解决了呢?褪去实现上的种种细节,从更高的角度观察这个算法,它的思路是怎么样的呢?

和冬冬讨论了半天,似乎找到了一个比较靠近此算法根本动机的理解方向。如下:

简化

此问题中,框的左端和右端同时在向右移动。这时,要在任意时刻用O(1)的时间获得框内最小值(最大值同理,故仅以最小值为例)并不容易。但是,如果假设这个框是可伸缩的,将其一端固定,仅移动另外一端,任意时刻能否在O(1)的时间内获得最小值呢?

稍加思考,就发现要找到这样的算法是很容易的(事实上在我最初考虑时,就是试图在这样一个算法的基础上进行优化的)。

假如这个框是左端固定,右端不断向右移动的(称之为左定右动框)。对于框内的每个数,有一个对应指针指向框内它左边(包括自身)所有数中最小者。这样,框内最小值就是框内最右端元素对应的指针所指向的元素。如在下图中,最小元素就是右端7对应指针所指向的元素6。

image0

当框的右端向右扩展时,可以通过递推获得新元素对应指针应指向的元素。以上图为例。加入2时,由7对应的指针可知原框中最小值为6,而6>2,所以新元素2对应的指针应指向自己。

image1

加入8时,由2的指针知原框中最小值为2,而2<8,所以新元素8对应指针应指向2的指针所指向的元素2。

image2

其余如法炮制。

image3

可见,在框左端固定、右端不断扩展时,任意时刻都能在常数时间内确定框内元素的最小值。(不仅如此,即使需要让右端向左收缩,也能在常数时间内,通过最右端元素指针获得得到收缩后框内所剩元素的最小值。) 整个过程演示如下(先扩张后收缩):

image4

演示中的收缩操作在当前问题中并无必要。演示出来是为了说明无论右端如何移动,只要左端不动,就可以在任意时刻立刻得到最小值。同时也是为了与下面一个演示保持一致。

如果一个框右端固定,左端收缩(称之为右定左动框),也可以在任意时刻花费常数时间获得框内的最小元素。过程和上面左右对称。具体地说,每个元素对应一个指针,指向框内它右边(包括自身)所有数中最小者。首先需要从右到左计算出各个元素对应的指针。这个过程类似于将框的左端由右向左扩展。计算完毕后就可以在收缩左端的过程中在常数时间内获得最小元素了。

演示如下(先扩张后收缩,可以看到完全和上面对称):

image5

对于当前问题,在“扩张”过程中并不需要求最小值,而仅仅需要计算出指针来为收缩过程作准备。这里在全过程中标注出最小值是为了说明任意时刻都有能力得到它,也为了与上一个演示保持一致。

上面拉拉杂杂说了一堆,只为了说明:如果框的一端固定,仅移动另外一端,则在此过程中可以仅花费常数时间获得框内的最小元素。针对左定右移、右定左移两种情况的算法是彼此对称的。

最后顺带提一点实现细节,希望不会影响你对整体的理解。上面所使用的指针也可以用索引号来代替,这里使用指针是为了显得更形象。事实上,不保存索引或指针而直接保存最小的“值”也是可行的,但是并不推荐。设想,如果每个元素不是数而是四五米长的字符串(>_<),偏序关系使用字符串长度的比较,那么如果不保存指针/索引而保存值,所带来的元素复制开销恐怕不是你想要的。

推广

怎样把上面只允许一端移动的解法推广到同时允许两端移动呢?

一种想法是,将以上二者合二为一。具体地说,将框内的数看成左右两部分,左边一部分看成右定左动的,右边一部分看成左定右动的。这样,在左边收缩、右边扩张的过程中,左右两部分都可以在常数时间内得到最小元素。取两个最小元素中更小者,即为整个框中的最小元素。

OK,这就是O(N)算法的基本思路了。回到原题目,下面看一个例子。

假设我们要处理的是这么一串数:

3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3

框的大小为5。

首先,把最先被框住的5个数看成被一个右定左动的框框住,这5个数右边看成是一个空的左定右动框。当然,首先需要计算出开始这5个元素对应的指针:

image6

接下来,左边的右定左动框收缩,右边的左定右动框扩张。在此过程中,框在框中的M个元素的最小者可以在常数时间内获得。

image7

到左边部分收缩至空时就没有办法继续收缩了。怎么继续这个过程呢?

解决方法是,将右端含有M个元素的左定右动框重新处理为右定左动框,并在右边再放上一个空左定右动框:

image8

接下来继续这个过程就行了。下面是全过程的演示:

image9

你可能会对每次将右边的左定右动框重新处理为左边的右定左动框(有点晕—)时计算指针造成的额外开销存有疑虑。然而,每次重新计算时需要处理M个元素的指针,每隔M个元素才会进行一次这样的处理,N/M*M仍然为N,并不会升高复杂度的阶。换句话说,每个元素至多被重新计算两次指针,所以总体复杂度仍然为O(N)。

以上就是整个解法。

关于栈

我们可以把右定左动框看成是一个底在右顶在左的栈,左端向左扩张看成是向栈push元素,左端向右收缩看成是栈在pop元素。左定右动框亦然。前面提到,两种框上的操作是对称的;如果把它们都看成栈,则push和pop时的操作完全一致。这样就将两种框对称的操纵统一在了同一个数据结构上,使得实现起来更为简洁。

这就是对开始所引用那段算法描述的解释。

问题的扩展

更进一步,我们还可以使用类似的方法处理此问题的变种。如,对于一个队列,随意进行入队出队操作(相当于木框的宽度不再固定为M,其两端也不同时向右移动),求在任意时刻队列中的最小元素。或者,一个双端队列,在两端随意进行入队出队操作,求任意时刻队列中的最小元素。等等。

最后顺便一提,在搜索此题资料时发现这个问题似乎涉及到数据流的处理算法。这个方面我一无所知,没办法站在那样一个高度阐述,抱歉。