Tìm số âm đầu tiên trong mỗi cửa sổ kích thước k bằng C++

Mô tả bài toán

Cho mảng và kích thước cửa sổ k. Với mỗi cửa sổ trượt, in số âm đầu tiên (hoặc 0 nếu không có).

Ví dụ

arr={-2,2,-1,4,3,-6}, k=2 → Output: -2, -1, -1, 0, -6.

Giải thuật

• Naive O(N×k): Duyệt từng cửa sổ tìm số âm đầu.
• Sliding Window + Deque O(N): Deque lưu chỉ số các số âm trong cửa sổ. Trượt: bỏ chỉ số ngoài cửa sổ, thêm chỉ số mới nếu âm. Phần tử đầu deque là số âm đầu tiên.

Mã nguồn C++ (Deque)

#include <bits/stdc++.h>
using namespace std;

void findFirstNegIntWindowK(int arr[], int n, int k) {
    deque<int> dq;
    for (int i=0; i

First negative integer in each with of size 2 is -2 -1 -1 0 -6