We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. C++
  3. STL
  4. Deque-STL
  5. Discussions

Deque-STL

Sort by

recency

|

459 Discussions

|

  • dangis_bakutis
     + 0 comments
    #include <iostream>
#include <deque>
#include <vector>
using namespace std;

void printKMax(const vector<int>& arr, const int n, const int k)
{
    deque<int> dq;
    for (int i = 0; i < n; i++)
    {
        if (!dq.empty() && dq.front() == i - k)
            dq.pop_front();

        while (!dq.empty() && arr.at(dq.back()) < arr.at(i))
            dq.pop_back();

        dq.push_back(i);

        if (i >= k - 1)
            cout << arr[dq.front()] << " ";
    }
    cout << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t > 0)
    {
        int n, k;
        cin >> n >> k;
        vector<int> arr;
        for (int i = 0; i < n; i++)
        {
            int ai;
            cin >> ai;
            arr.push_back(ai);
        }
        printKMax(arr, n, k);
        t--;
    }
    return 0;
}

  • habib_motavassel
     + 0 comments

    Hi everyone!

    I wanted to share my well-commented solution for the Sliding Window Maximum problem. I explain the deque logic and how to achieve O(n) complexity.

    Check it out on GitHub: https://github.com/habibma/SlidingWindowMaximum

  • charlie_the_sit1
     + 0 comments

    I think to force deque use there should be a test for the worst case (decreasing array). Using quick-bench.com you can see that although with a random array the int algorithm is between roughly 1.3x and 6x faster than the deque implementation, when the values in the array are always decreasing, the complexity quickly becomes closer to 0(n* k) in the int implementation. Meaning that the bigger the k the slower the code relative to the deque implementation and in my test up to 270x slower for a decreasing array from 4999 to 0 and a k of 2000. If you want to play around here's the benchmark I used https://github.com/cegranger/statquest-cpp/blob/main/benchmarks/bench_moving_max.cpp

  • ludovic_tirtiaux
     + 0 comments

    I didn't know if using deque was mandatory, so I went oldschool with some optimizations to avoid a full n² complexity:

    void printKMax(int arr[], int n, int k){
	//Write your code here.
    int max = 0;
    int pos = 0;
    
    for (int i = 0; i < k; i++) {
        if (arr[i] > max) {
            pos = i;
            max = arr[pos];
        }
    }
    
    cout << max;
                
    for (int j = k; j < n; j++) {
        if (j - k < pos) {
            if (arr[j] > max) {
                max = arr[j];
                pos = j;
            }
        } else {
            max = 0;
            for (int i = 1; i <= k; i++) {
                if (arr[j - k + i] > max) {
                    pos = j - k + i;
                    max = arr[pos];
                }
            }
        }

        cout << " " << max;
    }
    
    cout << endl;
}

  • yashdeora98294
     + 0 comments

    Here is Deque-STL problem solution in C++ - https://programmingoneonone.com/hackerrank-deque-stl-solution-in-cpp.html