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

题目

MAX最值差 - 蓝桥云课

---

问题描述

给定一个长度为 $N$ 的数组 $a$ 和一个常数 $k$，数组的值分别为 $a_1, a_2, \dots, a_N$。

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

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

输入格式

输入第 $1$ 行包含两个正整数 $N, k$。

第 $2$ 行包含 $N$ 个非负整数 $a_1, a_2, \dots, a_N$，表示数组 $a$ 元素的值。

$1 \le N, k \le 10^6, -10^6 \le a_i \le 10^6$。

输出格式

输出共 $1$ 行，包含一个整数，表示答案。

样例输入

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);
    }
}