生成窗口最大值数组

  第一种暴力查找算法，复杂度O(nm)，利用双端队列可达到平均O(n)

#include <iostream>
#include <deque>
using namespace std;
//暴力查找 O(nm)
void getMaxWindow(int arr[], int n, int w,int* ret) {
       if (n < w || !ret)
              return;
       int rLen = n - w + 1;
       int* p = arr;
       for (int i = 0; i < rLen; ++i,++p) {
              int max = *p;
              for (int j = 1; j < w; ++j) {
                     if (max < *(p + j))
                           max = *(p + j);
              }
              *ret++ = max;
       }
}
//双端队列 O(n)
void getMaxWindowFast(int arr[], int n, int w, int* ret) {
       if (n < w || !ret)
              return;
       int rLen = n - w + 1;
       deque<int> dq;//存储的是元素的Index
       unsigned int it = 0;
       for (int i = 0; i < n; ++i) {
              while (!dq.empty() && arr[*(dq.end() - 1)] < arr[i])
                     dq.pop_back();//从队尾开始比较，把凡是小于当前值的所有元素都去掉
              dq.push_back(i);//将当前值加入队尾，即如果dq的len不是1，那么当前值就成了最小值
              if (!dq.empty() && dq.front() == i - w)
                     dq.pop_front();//顶部的值已经不再属于当前窗口
              if (i >= w - 1) {//窗口还没开始滑动之前，只有一个ret，开始滑动之后，每一次循环就有一个最大值
                     ret[it++] = arr[dq.front()];
              }
       }
}
int main() {
       int arr[] = { 4,3,5,4,3,3,6,7 };
       int w = 3;
       int* ret = new int[8 - w + 1];
       getMaxWindowFast(arr, 8, w, ret);
       for (int i = 0; i < 8 - w + 1; ++i) {
              cout << ret[i] << endl;
       }
       delete[] ret;
       system("pause");
       return 0;
}