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

Question

我正在努力解决关于 hackerrank deque-stl 的问题。我已经实现了一种算法，该算法在 windows 中找到最大元素并存储其索引，然后使用前一个 window 中最大元素的索引来查找下一个 window 中的最大元素] 仅当最大元素的索引位于下一个 window 的索引之间时。使用这个算法和评论中提到的建议，我已经实现了这个更新的算法，但我仍然得到 Wrong Answer 错误。

#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

简介

为了有效地解决这个问题，请跟踪当前或后续滑动中可能为最大值的元素 windows。

算法

在你的 Hackerrank 练习中，你应该使用 std::deque 来有效地解决问题。所以，我建议不要偏离这个并使用 std::deque.

解决它

让我们考虑一个例子。给定一个数组arr = [4, 3, 4, 2, 5]和windowk = 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] 在这个滑动 window 中较小，但在没有 arr[0] 的另一个滑动中可能是最大的。
```
Step 3
arr:     |4 3 4| 2 5
queue :  |  2  |
```
在最后一步中，我们只在队列中保留了 2。为什么？因为 arr[2] 不小于
arr[0] 或 arr[1]。因此，将这些索引保持为最大值没有意义此子数组中的值仍为 arr[2].

由于第一次滑动window完成，打印arr[queue.front()]。队列的第一个元素对应子数组中最大元素的索引。
一旦第一个 3 元素被处理，在每次迭代中滑动 window 开始向右移动：
```
arr:      4 |3 4 2| 5
queue :     | 2 3 | 
```
打印 arr[2] 作为最大值。同样，队列的第一个元素对应于子数组中最大元素的索引。 3被保留在队列中是因为它潜在地可以对应下一次滑动中最大值的索引windows。
```
arr:      4 3 |4 2 5|
queue :       |  4  |
```
最后，4 仍然是唯一的元素，因为 2 无论如何都会弹出（它不属于当前的 window）和 arr[4] >= arr[3] 所以它保留它没有意义。

总结一下，算法的步骤如下：

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

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

希望现在很清楚如何实施这个想法。解决方案的时间复杂度为 O(n)。 space 复杂度也是 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";
}

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

Given an array and integer k find maximum value in each subarray of size k

c++

algorithm

data-structures

stl

deque

简介

算法

代码