用双端队列容器求滑动窗口的最大值和最小值

双端队列（deque，全称Double Ended Queue）是一种可以在两端进行插入和删除元素的数据结构，它既支持在头部添加和移除元素，也支持在尾部进行操作。在解决滑动窗口问题时，可以利用这种数据结构来高效地找到给定区间内的最大值和最小值。

以下是使用C++的`std::deque`实现滑动窗口最大值和最小值的一种常见方法：

#include <deque>
#include <algorithm>

// 定义滑动窗口的最大值和最小值
struct WindowMinMax {
    std::deque<int> window; // 使用deque作为窗口
    int max_val, min_val;

    void add(int num) {
        // 添加新元素到窗口
        window.push_back(num);

        // 更新最大值和最小值
        if (window.size() > 1) { // 窗口大小大于1
            max_val = std::max(max_val, num);
            min_val = std::min(min_val, num);

            // 如果窗口满，移除左侧的第一个元素并更新最大值和最小值
            if (window.front() == num - (window.size() - 1)) {
                window.pop_front();
                max_val = std::max(window.front(), max_val);
                min_val = std::min(window.front(), min_val);
            }
        } else {
            max_val = num;
            min_val = num;
        }
    }

    void remove(int num) {
        // 移除指定元素
        if (!window.empty() && window.back() == num) {
            window.pop_back();
            if (window.empty()) {
                max_val = min_val = INT_MIN; // 如果窗口为空，设最大值和最小值为整数最小
            } else {
                max_val = *std::max_element(window.begin(), window.end());
                min_val = *std::min_element(window.begin(), window.end());
            }
        }
    }
};

int main() {
    WindowMinMax window;
    // 示例操作：add(5), add(8), remove(5), add(10), remove(8)
    window.add(5); // 窗口[5]
    window.add(8); // 窗口[5, 8]
    window.remove(5); // 窗口[8]
    window.add(10); // 窗口[8, 10]
    window.remove(8); // 窗口[10]

    // 结果：max_val = 10, min_val = 8
    return 0;
}