[STLC++Queue] firstNegative

Bài tập.

Cho một mảng các số nguyên arr và một số nguyên dương k. Hãy viết hàm trả về các phần tử âm đầu tiên trong cửa số k. Nếu không tồn tại số âm nào output 0. Xem ví dụ để hiểu rõ đề bài hơn.

Ví dụ:

• Với arr = [-8 2 3 -6 10], k = 2 thì các cửa số lần lượt chứa các giá trị: [-8, 2], [2, 3], [3, -6], [-6, 10] nên kết quả trả về sẽ có dạng firstNegative(arr, k) = [-8, 0, -6, -6]

Hướng dẫn.

• Bài này có thể duyệt trâu với độ phức tạp O(n*k) nhưng có thể áp dụng queue để giảm độc phức tạp xuông còn O(n).
• Sử dụng queue<int> để lưu trữ chỉ số các phần tử âm trong cửa sổ.

Code mẫu:

vector<int> firstNegative(vector<int> a, int k)
{
    queue<int> st;
    int n = a.size();
    for (int i = 0; i < k - 1; i++) {
        if (a[i] < 0) st.push(i);
    }
    vector<int> res;
    for (int i = k - 1; i < n; i++) {
        if (a[i] < 0) st.push(i);
        while (!st.empty() && st.front() < i - k + 1) st.pop();
        res.push_back(st.empty() ? 0 : a[st.front()]);
    }
    return res;
}