生成窗口最大值数组

【说明】：

　　本文是左程云老师所著的《程序员面试代码指南》第一章中“生成窗口最大值数组”这一题目的C++复现。

　　本文只包含问题描述、C++代码的实现以及简单的思路，不包含解析说明，具体的问题解析请参考原书。

　　感谢左程云老师的支持。

【题目】：

　　有一个整形数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边，窗口每次向右边滑动一个位置。

　　例如，数组为 {4,3,5,4,3,3,6,7}，窗口大小为3时：

　　[4 3 5] 4 3 3 6 7 窗口中的最大值为5

　　4 [3 5 4] 3 3 6 7 窗口中的最大值为5

　　4 3 [5 4 3] 3 6 7 窗口中的最大值为5

　　4 3 5 [4 3 3] 6 7 窗口中的最大值为4

　　4 3 5 4 [3 3 6] 7 窗口中的最大值为6

　　4 3 5 4 3 [3 6 7] 窗口中的最大值为7

　　如果数组长度为 n，窗口大小为 w，则一共产生 n-w+1 个窗口的最大值。

　　请实现一个函数：

　　输入：整型数组 arr，数组大小 len，窗口大小 w。
　　输出：一个长度为 n-w+1 的数组 res，res[i]表示每一种窗口状态下的最大值。

【思路】：

　　使用双端队列来记录一个窗口中，arr 数组的最大值序号。

【编译环境】：

　　CentOS6.7（x86_64）

　　gcc 4.4.7

【实现】：

　　实现及测试代码：

/*
 *文件名：maxWindow.cpp
 *作者：
 *摘要：生成窗口最大值数组的实现及测试代码
 */
 
#include <iostream>
#include <deque>

using namespace std;

/*
 *函数介绍：生成窗口最大值数组的实现代码
 *输入参数：arr为源数组；len为数组的长度；w为窗口的大小
 *输出参数：
 *返回值：指向窗口最大值数组的指针
 */
int* getMaxWindow(int arr[],int len,int w)
{
    if(NULL == arr || w < 1 || len < w)
        return NULL;
    deque<int> qmax;
    int *res = new(nothrow) int[len-w+1];
    if(NULL == res)
    {
        cout << "Memory allocated failed!" << endl;
        return NULL;
    }
    int index = 0;
    for(int i=0;i<len;i++)
    {
        while(!qmax.empty() && arr[qmax.back()] <= arr[i])
            qmax.pop_back();
        qmax.push_back(i);
        if(qmax.front() == i-w)
            qmax.pop_front();
        if(i >= w-1)
            res[index++] = arr[qmax.front()];
    }
    return res;    
}

int main()
{
    int arr[] = {4,3,5,4,3,3,6,7};
    int *res = getMaxWindow(arr,8,3);
    for(int i=0;i<6;i++)
        cout << res[i] << endl;
    return 0;
}

View Code

【关于双端队列的参考】：

　　STL系列之一：deque双向队列

　　C++ Deque(双向队列)

注：

　　转载请注明出处；

　　转载请注明源思路来自于左程云老师的《程序员代码面试指南》。