OJ滑动窗口最大值

题目

给定一个数组 nums, 有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧

你只可以看到在滑动窗口内的 k 个数字.滑动窗口每次只向右移动一位

输入nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

输出[3, 3, 5, 5, 6, 7]

思路

此处使用双向队列(deque)这个数据结构

当前滑动窗口最大值总是保存在队头, 队列里数据从大到小排列

若遇到值比队尾元素大, 则将从队尾开始比该值小的元素出队, 再将新值插入队尾中

若遇到值比当队尾元素小, 则直接插入到队尾

每次移动时, 判断队头元素(窗口最大值)是否在有效范围, 若不在, 将其从队列中删除

num = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

最后一行, 队头6由于已经不在窗口范围内故删除

代码

// v:待处理元素
// w:窗口大小
vector<int> maxSlideWindow(vector<int> v, int w) {
    vector<int> res;
    // q中储存的是v中元素的下标
    deque<int> q;
    
    // 处理前几个元素
    for (int i = 0; i < w; i++) {
        while (!q.empty() && v[i] >= v[q.back()]) {
            q.pop_back();
        }
        q.push_back(i);
    }
    for (int i = w; i < v.size(); i++) {
        // 队头元素为当前窗口最大值
        res.push_back(v[q.front()]);
        while
        // 当前元素大于队尾元素时删除队尾元素
        while (!q.empty() && v[i] >= v[q.back()]) {
            q.pop_back();
        }
        //当队头元素(最大值)不在窗口范围内时删除队头元素
        while (!q.empty() && q.front() <= i - w) {
            q.pop_front();
        }
        q.push_back(i);
    }
    res.push_back(v[q.front()]);
    return res;
}

补充

个人感觉难点在于删除队头元素(最大值)这一部分, 下面在进行说明

对于第i个元素, 若其是当前窗口的最大值, 那么其有效的范围为[i-w+1, i]

元素 : 2 3 4 2 6 2 5 1

下标 : 0 1 2 3 4 5 6 7

从第三个元素4开始:

• i = 2, v[2] = 4 ; i-w = -1 ; 有效范围:[0, 2] ; q.front = 2 ;q = [2]

• i = 3, v[3] = 2 ; i-w = 0 ; 有效范围:[1, 3] ; q.front = 2 ; q = [2, 3]

• i = 4, v[4] = 6 ; i-w = 1 ; 有效范围:[2, 4] ; q.front = 4 ; q = [4]

• i = 5, v[5] = 2 ; i-w = 2 ; 有效范围:[3, 5] ; q.front = 4 ; q = [4, 5]

• i = 6, v[6] = 5 ; i-w = 3 ; 有效范围:[4, 6] ; q.front = 4 ; q = [4, 6]

• i = 7, v[7] = 1 ; i-w = 4 ; 有效范围:[5, 7] ; 原本队列q = [4, 6, 7], 原本队头q.front = 4 <= i-w 不在有效范围内, 故出队;新队列q = [5, 6, 7], 新队头q.front = 6