每个窗口的最大减最小

👁️ 0 人浏览 💬 0 人评论 ❤️ 添加收藏

补全 main：对 {4, 2, 6, 1, 5, 3} 的每个长度为 3 的窗口，算「最大值 − 最小值」，输出其中最大的那个。window_max、window_min 都已经写好了。

本节模型：window_max / window_min 用 std::deque 存下标做单调队列，求每个长度为 k 的窗口的最值。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 补全：最小的出结果时机什么样的 DP 能这样优化 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

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

vector<int> window_max(const vector<int>& a, int k) {
    // 每个长度为 k 的窗口的最大值
    deque<int> dq;   // 存下标，对应的值从队首到队尾递减
    vector<int> res;
    for (int i = 0; i < (int)a.size(); i++) {
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front();
        if (i >= k - 1) res.push_back(a[dq.front()]);
    }
    return res;
}

vector<int> window_min(const vector<int>& a, int k) {
    // 每个长度为 k 的窗口的最小值
    deque<int> dq;   // 存下标，对应的值从队首到队尾递增
    vector<int> res;
    for (int i = 0; i < (int)a.size(); i++) {
        while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front();
        if (i >= k - 1) res.push_back(a[dq.front()]);
    }
    return res;
}

int main() {
    vector<int> a = {4, 2, 6, 1, 5, 3};
    vector<int> mx = window_max(a, 3), mn = window_min(a, 3);
    int best = 0;
    // TODO: 同一个窗口 i 的最大值是 mx[i]、最小值是 mn[i]，把差的最大值记到 best 里
    cout << best << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

每个窗口的最大减最小

更多题目

全部评论