侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【单调队列】MAX最值差【蓝桥杯】

GabrielxD
2023-02-05 / 0 评论 / 0 点赞 / 99 阅读 / 512 字
温馨提示:
本文最后更新于 2023-02-05,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

MAX最值差 - 蓝桥云课


问题描述

给定一个长度为 NN 的数组 aa 和一个常数 kk,数组的值分别为 a1,a2,,aNa_1, a_2, \dots, a_N

定义 F(i)F(i) 表示区间 [max(1,ik),i][max(1, i - k), i] 的最小值,G(i)G(i) 表示区间 [max(1,ik),i][max(1, i - k), i] 的最大值。

请你求出 G(i)F(i)G(i) - F(i) 的最大值。

输入格式

输入第 11 行包含两个正整数 N,kN, k

22 行包含 NN 个非负整数 a1,a2,,aNa_1, a_2, \dots, a_N,表示数组 aa 元素的值。

1N,k106,106ai1061 \le N, k \le 10^6, -10^6 \le a_i \le 10^6

输出格式

输出共 11 行,包含一个整数,表示答案。

样例输入

6 3 
4 6 5 2 3 1

样例输出

4

运行限制

  • 最大运行时间:2s
  • 最大运行内存:256M

解题

方法一:单调队列

思路

单调队列模板题,思路见:【单调队列】滑动窗口「单调队列经典应用」

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        in.nextToken();
        int k = (int) in.nval;
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            a[i] = (int) in.nval;
        }
        int[] que1 = new int[n], que2 = new int[n];
        int h1 = 0, t1 = -1, h2 = 0, t2 = -1;
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < n; ++i) {
            if (h1 <= t1 && i - que1[h1] > k) ++h1;
            while (h1 <= t1 && a[que1[t1]] >= a[i]) --t1;
            if (h2 <= t2 && i - que2[h2] > k) ++h2;
            while (h2 <= t2 && a[que2[t2]] <= a[i]) --t2;
            que1[++t1] = i;
            que2[++t2] = i;
            ans = Math.max(ans, a[que2[h2]] - a[que1[h1]]);
        }
        System.out.println(ans);
    }
}
0

评论区