這道題的意思是給定一個(gè)長(zhǎng)N的整數(shù)序列，用一個(gè)大小為K的窗口從頭開始覆蓋，問(wèn)第1-第N-K次窗口里面最大的數(shù)字和最小的數(shù)字。
剛開始還以為優(yōu)先級(jí)隊(duì)列可以做，發(fā)現(xiàn)無(wú)法刪除最前面的元素。估計(jì)用線段樹這個(gè)題也是可以解得。用這個(gè)題學(xué)了下單調(diào)隊(duì)列。
單調(diào)隊(duì)列正如其名，是一個(gè)從小到大排序的隊(duì)列，而且能夠保證所有的元素入隊(duì)列一次出隊(duì)列一次，所以平攤到每個(gè)元素的復(fù)雜度
就是O(1)。
對(duì)于這個(gè)題單調(diào)隊(duì)列的使用。以序列
1 3 -1 -3 5 3 6 7舉例。 1）元素類型：一個(gè)結(jié)構(gòu)體，包含數(shù)字大小和位置，比如(1，1），（3，2）。
2）插入操作：從隊(duì)尾開始查找，把隊(duì)尾小于待插入元素的元素全部刪除，再加入待插入的元素。這個(gè)操作最壞的
情況下是O(n)，但是我們采用聚集分析的方法，知道每個(gè)元素最多刪除一次，那么N個(gè)元素刪除N次，平攤到每一次
操作的復(fù)雜度就是O(1)了。
3）刪除隊(duì)首元素：比如本文給的那個(gè)題，窗口一直往后移動(dòng)，每一次移動(dòng)都會(huì)刪除一個(gè)元素，所以很可能隊(duì)首會(huì)是要
刪除的元素，那么每次移動(dòng)窗口的元素要進(jìn)行一次檢查，如果隊(duì)首元素失效的話，就刪掉隊(duì)首元素。
代碼的實(shí)現(xiàn)，我是包裝deque實(shí)現(xiàn)了一個(gè)模版類。速度很不好，居然跑了11s多才過(guò)，幸虧給了12s的時(shí)間，看status又500多ms
就過(guò)了的。估計(jì)數(shù)組實(shí)現(xiàn)會(huì)快很多。
代碼如下：
#include <stdio.h>
#include <deque>
#include <algorithm>
using namespace std;
#define MAX_N (1000000 + 100)
int nNum[MAX_N];
int nN, nK;
struct Small
{
int nValue;
int nIndex;
Small(
int nV,
int index):nValue(nV), nIndex(index) {}
bool operator < (
const Small& a)
const {
return nValue < a.nValue;
}
};
struct Big
{
int nValue;
int nIndex;
Big(
int nV,
int index):nValue(nV), nIndex(index) {}
bool operator < (
const Big& a)
const {
return nValue > a.nValue;
}
};
//單調(diào)隊(duì)列
template <typename T>
class Monoque
{
deque<T> dn;
public:
void Insert(T node)
{
int nPos = dn.size() - 1;
while (nPos >=0 && node < dn[nPos])
{
--nPos;
dn.pop_back();
}
dn.push_back(node);
}
int Top()
{
return dn.front().nValue;
}
void Del(
int nBeg,
int nEnd)
{
if (dn.size() > 0)
{
if (dn.front().nIndex < nBeg || dn.front().nIndex > nEnd)
{
dn.pop_front();
}
}
}
};
int main()
{
while (scanf("%d%d", &nN, &nK) == 2)
{
int i;
for (i = 0; i < nN; ++i)
{
scanf("%d", &nNum[i]);
}
Monoque<Small> minQ;
Monoque<Big> maxQ;
for (i = 0; i < nK; ++i)
{
minQ.Insert(Small(nNum[i], i));
}
for (i = 0; i < nN - nK; ++i)
{
printf("%d ", minQ.Top());
minQ.Insert(Small(nNum[i + nK], i + nK));
minQ.Del(i + 1, i + nK);
}
printf("%d\n", minQ.Top());
for (i = 0; i < nK; ++i)
{
maxQ.Insert(Big(nNum[i], i));
}
for (i = 0; i < nN - nK; ++i)
{
printf("%d ", maxQ.Top());
maxQ.Insert(Big(nNum[i + nK], i + nK));
maxQ.Del(i + 1, i + nK);
}
printf("%d\n", maxQ.Top());
}
return 0;
}