Hackerrank Deque-STL题目：滑动窗口最大值算法提交报错求助

Hey there! Let's figure out why your code is throwing that Wrong Answer error on Hackerrank's Deque-STL problem. I've gone through your implementation and spotted a few key issues that are likely causing the problem, plus I'll share a fixed version of your code to get you back on track.

1. Uninitialized & Mismanaged Global Variables #

You declared m and idx as global variables, which introduces two big problems:

• Default initialization to 0: If your test case includes negative numbers (e.g., [-5, -3, -2]), your initial check arr[k]>=m will fail (since 0 is larger than all negative values), leading to incorrect maximum values being stored.
• Stale values across test cases: If you run multiple test cases, idx will retain its value from the previous case, causing wrong comparisons in subsequent windows.

2. Missing Index Updates in Critical Branches #

In the else block of your maxinwindow function, you set m to the larger of the first two elements in the window, but you don't update idx to match this new maximum. For example:

if(arr[start]>=arr[start+1])
    m=arr[start]; // idx stays as old value!
else
    m=arr[start+1]; // idx still not updated!

This means idx will keep pointing to a value outside the current window, leading to incorrect checks in future iterations.

3. Risk of Stack Overflow with Fixed-Size Arrays #

Your code uses int arr[100000]; which is allocated on the stack. Stack space is limited (usually a few MB), so large input sizes can cause a stack overflow, leading to unexpected behavior or crashes.

4. Incomplete Window Traversal (Minor Edge Case) #

In the else block, you start comparing from start+2, but if the window size is exactly 2, this loop never runs. While this doesn't break functionality for size-2 windows, it's inconsistent and could lead to confusion if you modify the code later.

Here's a revised version of your code that addresses all these issues, plus some optimizations for Hackerrank's input constraints:

#include <iostream>
#include <vector>
using namespace std;

// Returns the max value in the current window, updates the max index via reference
int get_window_max(const vector<int>& arr, int start, int end, int& prev_max_idx) {
    int current_max;
    // Reuse previous max if it's still in the current window
    if (prev_max_idx >= start) {
        if (arr[prev_max_idx] >= arr[end]) {
            current_max = arr[prev_max_idx];
        } else {
            current_max = arr[end];
            prev_max_idx = end;
        }
    } else {
        // Scan the entire window to find new max
        current_max = arr[start];
        prev_max_idx = start;
        for (int k = start + 1; k <= end; ++k) {
            if (arr[k] >= current_max) {
                current_max = arr[k];
                prev_max_idx = k;
            }
        }
    }
    return current_max;
}

int main() {
    // Speed up input for large test cases
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int q;
    cin >> q;
    while (q--) {
        int size, window_size;
        cin >> size >> window_size;
        vector<int> arr(size);
        for (int j = 0; j < size; ++j) {
            cin >> arr[j];
        }
        
        // Handle window size 1 case
        if (window_size == 1) {
            for (int num : arr) {
                cout << num << " ";
            }
            cout << "\n";
            continue;
        }
        
        // Initialize first window's max
        int prev_max_idx = 0;
        int current_max = arr[0];
        for (int k = 1; k < window_size; ++k) {
            if (arr[k] >= current_max) {
                current_max = arr[k];
                prev_max_idx = k;
            }
        }
        cout << current_max << " ";
        
        // Process remaining windows
        for (int k = 1; k <= size - window_size; ++k) {
            int start = k;
            int end = k + window_size - 1;
            current_max = get_window_max(arr, start, end, prev_max_idx);
            cout << current_max << " ";
        }
        cout << "\n";
    }
    return 0;
}

Key Improvements #

• No more global variables: prev_max_idx and current_max are local to each test case, avoiding stale values and initialization issues.
• 0-based indexing: Aligns with C++'s standard array/vector behavior, reducing off-by-one errors.
• Vector instead of fixed array: Prevents stack overflow for large input sizes.
• Input speed optimizations: ios_base::sync_with_stdio(false); cin.tie(nullptr); ensures your code doesn't time out on large test cases.
• Full window scan in fallback: The else block now scans the entire window from start to end, ensuring no maximum value is missed.

This should resolve the Wrong Answer errors you're seeing. Give it a try on Hackerrank!

内容的提问来源于stack exchange，提问作者Shantanu