下载掌阅APP，畅读海量书库
立即打开
有一种密钥：给出一个长度为 n 的序列 A ， A 中所有长度为 m 的连续子序列的最大值即密钥。例如 n ＝7，有数组{8,7,1,5,9,3,6}，当 m ＝3时，则密钥为87999，获取密钥的过程如图3.5所示。
图3.5
第一行为两个整数，即 n 和 m （1＜ n ＜90000）。
第二行为 n 个整数。
输出密钥值。
7 3
8 7 1 5 9 3 6
87999
要高效率解决此题，一般会使用单调队列。顾名思义，单调队列是使队列中的元素保持单调递增（减），而保持的方式就是通过“插队”把队尾破坏了单调性的元素全部挤掉。可以这么想象：有一长串队伍排队买票，忽然来了一个人高马大的家伙，一看这么长的队伍，心情急躁，于是就从队尾开始，看到好欺负的就将其赶出队列……如此一路向前，直到遇到比他更强壮的家伙为止。
本题样例的运行过程如表3.1所示。
表3.1
参考程序如下。
