滑动窗口最大问题中的分段故障

Question

我曾尝试在Hackerrank（Deque-stl）上使用双端队列问题来解决最大滑动窗口问题。我遵循this链接上给出的算法。我不想复制解决方案，因此尝试尝试编写自己的解决方案。但是我的代码给我“细分错误”，我不明白我的代码有什么问题。谁能解释我的代码中的错误吗？

void printKMax(int arr[], int n, int k)
{
    deque<int> q;
    int l=0,j=k-1;
    q.push_back(l);
    while(j!=n)
    {
        for(;l<j;)
        {
            while((arr[l+1]>arr[q.back()])&&(!q.empty()))
                q.pop_back();
            q.push_back(++l);
        }
        cout<<arr[q.front()]<<" ";
        j++;
        while(q.front()<=j-k)
            q.pop_front();
    }
    cout<<"\n";
}

Answer 1

我不确定算法是否正确，但是有两行可能导致分割错误：

while((arr[l+1]>arr[q.back()])&&(!q.empty()))

原因是您在q.back()之前先检查q.empty()是否为空，否则会出现错误。更改为：

while((!q.empty())&&(arr[l+1]>arr[q.back()]))

这样，它将首先检查是否为空，并在检查q.back()并给出分段错误之前制动循环是否为空。

第二行是：

while(q.front()<=j-k)
    q.pop_front();

我认为您应该像第一行一样检查它是否为空。