Judge：http://dsalgo.openjudge.cn/stackqueue/7/ 题意：给定一个长度为n（n<=10^6）的数组。有一个大小为k的滑动窗口从数组的最左端移动到最右端。求滑动窗口在每个位置时的最大值和最小值。 总时间限制：12000ms
可以使用单调队列来做这道题。
#include <cstdio> #include <deque> using namespace std; #define MODE_MAX 1 #define MODE_MIN 0 int g_iNumTot, g_iWndLen, g_arrNum[1000010]; deque<int> g_queHumMin, g_queHumMax; void InsertQueue(deque<int> & theQueue, int iMode, int iData) { int iSize = theQueue.size(); for (int i = 1; i <= iSize; i++) if (iMode == MODE_MAX && theQueue.back() < iData) theQueue.pop_back(); else if (iMode == MODE_MIN && theQueue.back() > iData) theQueue.pop_back(); else break; theQueue.push_back(iData); } int g_arrResMin[1000000], g_arrResMax[1000000]; int main() { scanf("%d%d", &g_iNumTot, &g_iWndLen); int iNum; for (int i = 1; i <= g_iNumTot; i++) { scanf("%d", &iNum); g_arrNum[i] = iNum; if (i <= g_iWndLen) { InsertQueue(g_queHumMin, MODE_MIN, iNum); InsertQueue(g_queHumMax, MODE_MAX, iNum); if (i < g_iWndLen) continue; } if (i > g_iWndLen) { if (g_queHumMin.front() == g_arrNum[i - g_iWndLen]) g_queHumMin.pop_front(); if (g_queHumMax.front() == g_arrNum[i - g_iWndLen]) g_queHumMax.pop_front(); InsertQueue(g_queHumMin, MODE_MIN, iNum); InsertQueue(g_queHumMax, MODE_MAX, iNum); } g_arrResMin[i - g_iWndLen] = g_queHumMin.front(); g_arrResMax[i - g_iWndLen] = g_queHumMax.front(); } for (int i = 0; i < g_iNumTot - (g_iWndLen - 1); i++) printf("%d ", g_arrResMin[i]); printf("\n"); for (int i = 0; i < g_iNumTot - (g_iWndLen - 1); i++) printf("%d ", g_arrResMax[i]); return 0; }
