Ошибка сегментации в проблеме максимума скользящего окна

Question

Я пытался решить максимум скользящего окна, используя задачу deque на Hackerrank ( Deque-stl ). Я следовал алгоритму, указанному на этой ссылке. Я не хотел копировать решение, поэтому попытался написать собственное решение. Но мой код дает мне «ошибку сегментации», и я не понимаю, что не так с моим кодом. Может кто-нибудь, пожалуйста, объясните ошибку в моем коде?

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

Я не уверен, что алгоритм правильный, но есть 2 строки, которые могут вызвать ошибку сегментации:

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

Причина в том, что вы проверяете q.back() до q.empty(), если он пустой результат будет неопределенным поведением. Измените это на:

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

Таким образом, он проверит, является ли он первым пустым, и тормозит l oop, если он пуст, перед проверкой q.back() и выдачей ошибки сегментации.

Вторая строка:

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

Я думаю, вы должны проверить, если она пуста, как первая строка.