生成窗口最大值数组

浅浅的花香味﹌ 2022-07-24 09:29 116阅读 0赞

## 生成窗口最大值数组 – C++ ##

题目  
给出一个整形数组，例如arr = \{5,4,3,5,6,7,6\}，窗口大小为w=3，窗口每次向右移动一位，输出每个窗口中最大值组成的数组。

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

则输出的数组为`{5,5,6,7,7};`

--------------------

## 解题思路及C++代码 ##

对于一个给定的数组，求得的最终数组长度可以确定是arr.length - w +1,。  
本题使用双端队列来更新最大值下标，并同时将最大值存入数组中。

--------------------

算法C++代码：

class Solution
    {
    public:
        static int* getMaxWindow(int arr[], int len, int w)
        {
            if (len == 0 || w < 1 || len < w)
                return NULL;
    
            deque<int>* qmax = new deque<int>();
    
            int *temp = new int[len - w + 1];
            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);
    
                //队头下标为i-w  说明下标已过期
                if (qmax->front() == i - w)
                    qmax->pop_front();
    
                //够w个数据后开始给temp赋值，i从0开始
                if (i + 1 >= w)
                    temp[index++] = arr[qmax->front()];
            }
            delete qmax;
            qmax = NULL;
            return temp;
        }
    };

--------------------

## 算法测试用例： ##

#include <iostream>
    #include <deque>
    using namespace std;
    
    class Solution
    {
    public:
        static int* getMaxWindow(int arr[], int len, int w)
        {
            if (len == 0 || w < 1 || len < w)
                return NULL;
    
            deque<int>* qmax = new deque<int>();
    
            int *temp = new int[len - w + 1];
            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)
                    temp[index++] = arr[qmax->front()];
            }
            delete qmax;
            qmax = NULL;
            return temp;
        }
    };
    
    void printElem(int arr[], int len)
    {
        for (int i = 0; i < len; i++)
            cout << arr[i] << " ";
        cout << endl;
    }
    
    int main()
    {
        int arr[] = { 4, 3, 5, 4, 3, 3, 6, 7 };
        int len = sizeof(arr) / sizeof(int);
        int w = 4;
        int len2 = len - w + 1;
        int* p = Solution::getMaxWindow(arr, len, w);
    
        cout << "原数组: " << endl;
        printElem(arr, len);
        cout << "输出：" << endl;
        printElem(p, len2);
    
        delete p;
        p = NULL;
        system("pause");
    }

运行结果：

原数组:
    4 3 5 4 3 3 6 7
    输出：
    5 5 5 6 7
    请按任意键继续. . .