队列求滑动窗口中最大值中的最小值

假设滑动窗口的大小为k，我们可以使用一个双端队列来解决这个问题。队列中存储窗口中的元素下标，队列中的元素按照从大到小的顺序排列。

具体的算法如下：
1. 首先，将窗口中的前k个元素的下标依次加入队列中。
2. 接着，从第k+1个元素开始，依次处理每个元素。
3. 对于每个元素，首先判断队列中的队首元素是否已经越过了窗口的左边界。如果是，则将队首元素弹出队列。
4. 然后，将当前元素的下标加入队列中。
5. 接下来，如果队列中的元素个数超过了k个，则将队尾元素弹出队列。
6. 最后，如果当前处理的元素的下标已经大于等于k-1，则队列中的队首元素就是当前窗口中的最大值。将这个最大值记录下来，并与之前的最小值进行比较，更新最小值。

时间复杂度为O(n)，其中n为数组的长度。

相关问题

队列求滑动窗口中最大值中的最小值的代码

以下是使用双端队列实现求滑动窗口中最大值中的最小值的代码：

from collections import deque

def min_of_max_sliding_window(nums, k):
    n = len(nums)
    if k > n:
        return -1

    # 双端队列用于存储窗口中的元素下标
    q = deque()

    # 将窗口的第一个元素加入队列
    for i in range(k):
        while q and nums[i] >= nums[q[-1]]:
            q.pop()
        q.append(i)

    # 计算窗口中的最大值中的最小值
    res = nums[q[0]]
    for i in range(k, n):
        # 弹出队列中已经不属于窗口的元素
        while q and q[0] <= i - k:
            q.popleft()
        # 将当前元素加入队列
        while q and nums[i] >= nums[q[-1]]:
            q.pop()
        q.append(i)
        # 计算窗口中的最大值中的最小值
        res = min(res, nums[q[0]])

    return res

该函数接受一个整数列表和一个整数 `k`，返回滑动窗口中的最大值中的最小值。如果滑动窗口大小大于列表长度，返回 `-1`。

例如，对于列表 `[1,3,-1,-3,5,3,6,7]` 和整数 `k=3`，函数将返回 `3`，因为滑动窗口中的最大值是 `[3,3,5,5,6,7]`，其中最小值是 `3`。

队列求滑动窗口中最大值中的最小值的C++代码

以下是使用双端队列（deque）求解滑动窗口中最大值中的最小值的 C 代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 100000

int N, K;
int A[MAX_N + 1];
int Q[MAX_N + 1];
int head, tail;

// 初始化队列
void init() {
    head = 0;
    tail = -1;
}

// 将元素插入到队列尾部
void push(int idx) {
    // 如果队列非空，且队列尾部元素小于当前元素，则弹出队列尾部元素
    while (tail != -1 && A[Q[tail]] < A[idx]) tail--;
    // 将当前元素插入到队列尾部
    Q[++tail] = idx;
}

// 弹出队列头部元素
void pop() {
    head++;
}

// 获取队列头部元素
int front() {
    return Q[head];
}

int main() {
    scanf("%d %d", &N, &K);
    for (int i = 1; i <= N; i++) scanf("%d", &A[i]);

    init();
    int ans = A[1];
    for (int i = 1; i <= K; i++) push(i);
    for (int i = K + 1; i <= N; i++) {
        // 计算滑动窗口中最大值中的最小值
        ans = (ans > A[front()]) ? ans : A[front()];
        // 将滑动窗口中第一个元素弹出队列
        if (front() == i - K) pop();
        // 将当前元素插入队列
        push(i);
    }
    // 计算最后一个滑动窗口中的最大值中的最小值
    ans = (ans > A[front()]) ? ans : A[front()];

    printf("%d\n", ans);
    return 0;
}

该代码的时间复杂度为 O(N)。