c++ - 给定一个数组和整数 k 在每个大小为 k 的子数组中找到最大值

Question

我正在努力解决关于hackerrank deque-stl 的问题.我已经实现了一个算法，它在窗口中找到最大元素并存储它的索引，然后只有当最大元素的索引位于索引之间时，才使用前一个窗口中最大元素的这个索引来查找下一个窗口中的最大元素的下一个窗口。使用评论中提到的这个算法和建议，我已经实现了这个更新的算法，但我仍然收到错误的答案错误。

#include <iostream>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int m,idx;
void maxinwindow(int arr[], int start, int end)
{
    /*If the index of the maximum element in the previous window
    is between the indexes of next windows then no need to compare 
    elements that were in previous window */
    if(idx>=start)
    {
        if(arr[idx]>=arr[end])
        {
            m=arr[idx];
        }
        else
        {
            m=arr[end];
            idx=end;
        }
    }
    else
    {
        if(arr[start]>=arr[start+1])
            m=arr[start];
        else
            m=arr[start+1];
        for(int k=start+2;k<=end;k++)
        {
            if(arr[k]>=m)
            {
                m=arr[k];
                idx=k;
            }
        }
    }
}
int main()
{
    int arr[100000];
    int q;
    cin>>q;
    for(int i=1,size,ws;i<=q;i++)
    {
        m=0;
        cin>>size;  //Array size
        cin>>ws;   //Window Size
        //Entering The Elements In The Array
        for(int j=1;j<=size;j++)
        {
            cin>>arr[j];
        }
        //Boundary Condition i.e. Windows size is equal to 1
        if(ws==1)
        {
            for(int j=1;j<=size;j++)
            {
                cout<<arr[j]<<" ";
            }
        }
        else
        {
            for(int k=1;k<=ws;k++)
            {
                if(arr[k]>=m)
                {
                    m=arr[k];
                    idx=k;
                }
            }
            cout<<m<<" ";
            for(int k=2,j;k<=(size-(ws-1));k++)
            {
                j=(k+(ws-1));
                maxinwindow(arr,k,j);
                cout<<m<<" ";
            }
            cout<<endl;
        }
    }
}

Answer 1

介绍
为了有效地解决此问题，请跟踪当前或后续滑动窗口中可能是最大值的元素。
算法
在您的 黑客等级 练习，你应该使用std::deque为了有效地解决问题。因此，我建议不要偏离这一点并使用 std::deque 来解决它。 .
让我们考虑一个例子。给定一个数组 arr = [4, 3, 4, 2, 5]和窗口k = 3 , 如何在长度为 3 的每个子数组中找到最大值?

先过3元素并在队列中保留数组元素的相关索引。

Step 1
arr:     |4| 3 4 2 5
queue :  |0|

添加第一个元素的索引，因为队列为空。

Step 2
arr:     |4 3| 4 2 5
queue :  |0 1|

添加索引 1但保留 0如arr[0] > arr[1] .但是为什么要保留1然后？即使 arr11]在这个滑动窗口中较小它可以在另一个没有 arr[0] 的情况下是最大的.

Step 3
arr:     |4 3 4| 2 5
queue :  |  2  |

在最后一步，我们只保留了 2在队列中。为什么？因为arr[2]不小于arr[0]或 arr[1] .因此，将这些指数保持为最大值是没有意义的
此子数组中的值仍为 arr[2] .
由于第一个滑动窗口已经完成，打印arr[queue.front()] .队列的第一个元素对应于子数组中最大元素的索引。

一次先3元素被处理，在每次迭代中，滑动窗口开始向右移动:

arr:      4 |3 4 2| 5
queue :     | 2 3 | 

打印 arr[2]作为最大值。同样，队列的第一个元素对应于子数组中最大元素的索引。 3保留在队列中，因为它可能对应于下一个滑动窗口中最大值的索引。

arr:      4 3 |4 2 5|
queue :       |  4  |

最后，4仍然是唯一的元素，如 2无论如何都会弹出(它不属于当前窗口)和arr[4] >= arr[3]所以保留它没有意义。

总而言之，以下是算法的步骤:

对于第一个 k数组的元素，将可能的最大子数组元素的索引存储在队列中。在每个 i -th 迭代，如果元素的映射值不超过 arr[i]，则继续从队列中弹出元素然后推arr[i]进入队列。
最后，队列的第一个元素包含最大值的索引。

对于剩余的数组元素，在每次迭代 i ，弹出第一个元素front仅当它不再属于当前滑动窗口时 - i - front == k .然后，像以前一样，弹出映射值不超过 arr[i] 的索引。然后推 arr[i]进入队列(同样，在每次迭代结束时，队列包含最大值的索引)。

希望现在很清楚如何实现这个想法。解的时间复杂度为 O(n)。空间复杂度也是 O(n)。
代码

#include <algorithm>
#include <iostream>
#include <deque> 

void printKMax(int arr[], int n, int k){
    std::deque<int> queue;

    for (int i = 0; i < k; i++) {
        while (!queue.empty() && arr[queue.back()] <= arr[i]) {
            queue.pop_back();
        }

        queue.push_back(i);
    } 

    for (int i = k; i < n; i++) {
        std::cout << arr[queue.front()] << " ";

        // an element with index queue.front() no longer belong to ths window
        if (i - queue.front() == k) {
            queue.pop_front();  
        }

        // pop all elements that don't exceed arr[i] as they're no longer useful
        while (!queue.empty() && arr[queue.back()] <= arr[i]) {
            queue.pop_back();
        }  

        queue.push_back(i);
    }

    std::cout << arr[queue.front()] << "\n";
}