Deque-STL

  • + 0 comments

    A bit straightforward which passes all tests:

    void printKMax(int arr[], int n, int k) { std::deque subArr; int shift = 0; for(int a=0;a < k; ++a) subArr.push_back(arr[a]); // Get actual max value (iterator) auto maxval = std::max_element(subArr.begin(), subArr.end(), [](int a, int b){return a < b;}); // Get max value position int pos = maxval - subArr.begin(); cout << *maxval << ' ';

    while(shift + k < n){
        subArr.pop_front(); // Remove old value
        subArr.push_back(arr[shift + k]); // Add new value 
        pos--; // Move max value position back
    
        // If new value is greater than actual max
        if(subArr.back() > *maxval){
            pos = subArr.size() - 1;
            maxval = subArr.begin() + pos;
        }
        else if(pos < 0){ // If not and old value ran out of scope find new max value
            maxval = std::max_element(subArr.begin(), subArr.end(), [](int a, int b){return a < b;});
            pos = maxval - subArr.begin();
        }
    
        // Print new max value
        cout << *maxval << ' ';
        shift++;
    }
    
    cout << '\n';
    

    }