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

// 函数：返回每个滑动窗口的最大值
vector<int> maxSlidingWindow(const vector<int>& nums, int k) {
    int n = nums.size();                 // 数组总长度
    if (n == 0 || k <= 0) return {};

    vector<int> result;                  // 存储每个窗口的最大值
    deque<int> dq;                       // 双端队列，存储下标，从队首到队尾递减

    for (int i = 0; i < n; ++i) {
        // 1. 移除队首已经滑出窗口的元素（下标 < 窗口左边界 i - k + 1）
        while (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();              // 从队首弹出过期下标
        }

        // 2. 维护单调递减：从队尾移除所有值小于等于当前元素的元素
        //    因为这些元素在当前位置 i 之后不可能再成为最大值
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back();               // 从队尾弹出较小的元素
        }

        // 3. 当前元素下标入队（它一定比队尾所有元素大，保持单调递减）
        dq.push_back(i);

        // 4. 当窗口形成（i >= k-1）时，记录当前窗口最大值（队首）
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);  // 队首即最大值
        }
    }
    return result;
}

// 辅助函数：打印数组
void printVector(const vector<int>& vec) {
    cout << "[";
    for (size_t i = 0; i < vec.size(); ++i) {
        cout << vec[i];
        if (i != vec.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    vector<int> res = maxSlidingWindow(nums, k);
    cout << "原数组: ";
    printVector(nums);
    cout << "滑动窗口最大值: ";
    printVector(res);  // [3, 3, 5, 5, 6, 7]
    return 0;
}

from collections import deque

def max_sliding_window(nums, k):
    """返回滑动窗口最大值列表"""
    n = len(nums)                 # 数组长度
    if n == 0 or k <= 0:
        return []

    result = []                   # 存储结果
    dq = deque()                  # 双端队列，存储下标，单调递减（队首最大）

    for i in range(n):
        # 1. 移除队首过期下标（小于窗口左边界）
        while dq and dq[0] < i - k + 1:
            dq.popleft()

        # 2. 维护单调递减：弹出队尾所有比当前值小或相等的元素
        while dq and nums[dq[-1]] <= nums[i]:
            dq.pop()

        # 3. 当前下标入队
        dq.append(i)

        # 4. 窗口形成后记录最大值
        if i >= k - 1:
            result.append(nums[dq[0]])  # 队首最大

    return result

# 测试
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
res = max_sliding_window(nums, k)
print("原数组:", nums)
print("滑动窗口最大值:", res)  # [3, 3, 5, 5, 6, 7]

// 滑动窗口最小值，C++实现
vector<int> minSlidingWindow(const vector<int>& nums, int k) {
    int n = nums.size();
    if (n == 0 || k <= 0) return {};
    vector<int> result;
    deque<int> dq;  // 存储下标，单调递增（队首最小）
    for (int i = 0; i < n; ++i) {
        // 移除过期下标
        while (!dq.empty() && dq.front() < i - k + 1) dq.pop_front();
        // 维护单调递增：弹出队尾所有值大于等于当前值的元素
        while (!dq.empty() && nums[dq.back()] >= nums[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= k - 1) result.push_back(nums[dq.front()]);
    }
    return result;
}