问题

以最大连续和为例子说明

找出所有长度不超过 k 的连续子数组的最大和

给你一个长度为 n 的整数序列 {A1,A2,⋯,An}，要求从中找出一段连续的长度不超过 m 的子序列，使得这个序列的和最大。

输入格式

第一行为两个整数 n,m ；

第二行为 n 个用空格分开的整数序列，每个数的绝对值都小于 1000。

输出格式

仅一个整数，表示连续长度不超过 m 的最大子序列和。

输入输出样例

输入 #1

1
2
6 4
1 -3 5 1 -2 3

输出 #1

1
7

这道题是洛谷的 [U162981 最大连续和][https://www.luogu.com.cn/problem/U162981]

问题分析

上次我们说了滑动窗口的最大值最小值问题

那么这个问题就是它的进阶

接触过最大和和最小和的大伙肯定都能有一个直觉，就是能不能使用前缀和

很明显这道题是可以使用前缀和的

所以我们可以结合前缀和和单调队列来解决

计算前缀和数组 preSum，其中 preSum[i] = nums[0] + nums[1] + ... + nums[i-1]。

那么，子数组nums[j...i-1] 的和为 prefixSum[i] - prefixSum[j]。要找最大和，即对于每个 i，我们需要找到最小的 prefixSum[j]（其中 j >= i-k）。使得减数最小，最大和最大。

同理，如果我们要找最小子数组和，就需要找到最大的 prefixSum[j]，因为当被减数固定时，要让差值最小，就需要让减数尽可能大。

子数组和的计算转化为了固定被减数的减法问题。

维护一个单调递增的队列来存储 prefixSum 的索引，在滑动窗口内（长度不超过 m ）找到范围[i-m，i-1]内的最小值即可。

分析一下复杂度

  1. 时间复杂度：O (n)，每个元素最多入队和出队一次。
  2. 空间复杂度：O (n)，主要用于存储前缀和数组和队列。

示例代码

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 单调队列 O(n)
#include<iostream>
using namespace std;

const int N=300010;
int n,m,s[N];
int q[N],f[N];

int main(){
  scanf("%d%d",&n,&m);
  for(int i=1; i<=n; i++) 
    scanf("%d",&s[i]),s[i]+=s[i-1];
  
  for(int i=1,h=1,t=0; i<=n; i++){
    while(h<=t && q[h]<i-m) h++;
    while(h<=t && s[q[t]]>=s[i-1]) t--;
    q[++t]=i-1;
    f[i]=s[i]-s[q[h]];
  }

  int res=-2e9;
  for(int i=1; i<=n; i++) res=max(res,f[i]);
  printf("%d\n",res);
}

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line =  br.readLine().split(" ");

        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);

        int[] nums = new int[n];
        line = br.readLine().split(" ");
        for(int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(line[i]);
        }

        // 计算前缀和
        long[] preSum = new long[n + 1];
        for(int i = 0; i < n; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }

        Deque<Integer> deque = new ArrayDeque<>();
        // 初始时加入prefixSum[0]的索引
        deque.offerLast(0);
        long maxSum = Long.MIN_VALUE;

        for(int i = 1; i <= n; i++) {
            // 移除窗口外的元素，保证子数组长度不超过m
            while(!deque.isEmpty() && deque.peekFirst() < i - m) {
                deque.pollFirst();
            }

            // 当前窗口的最大和 = prefixSum[i] - 队列头部的最小前缀和
            maxSum = Math.max(maxSum, preSum[i] - preSum[deque.peekFirst()]);

            // 维护单调递增队列：移除队列尾部比当前前缀和大的元素
            while(!deque.isEmpty() && preSum[i] <= preSum[deque.peekLast()]) {
                deque.pollLast();
            }

            // 新元素入队
            deque.offerLast(i);
        }

        System.out.println(maxSum);
    }
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import sys
from collections import deque

def main():
    # 读取输入
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr += 1
    m = int(input[ptr])
    ptr += 1
    
    nums = []
    for i in range(n):
        nums.append(int(input[ptr]))
        ptr += 1
    
    # 计算前缀和
    pre_sum = [0] * (n + 1)
    for i in range(n):
        pre_sum[i + 1] = pre_sum[i] + nums[i]
    
    # 使用双端队列维护单调递增队列
    dq = deque()
    # 初始时加入pre_sum[0]的索引
    dq.append(0)
    max_sum = float('-inf')
    
    for i in range(1, n + 1):
        # 移除窗口外的元素，保证子数组长度不超过m
        while dq and dq[0] < i - m:
            dq.popleft()
        
        # 当前窗口的最大和 = pre_sum[i] - 队列头部的最小前缀和
        max_sum = max(max_sum, pre_sum[i] - pre_sum[dq[0]])
        
        # 维护单调递增队列：移除队列尾部比当前前缀和大的元素
        while dq and pre_sum[i] <= pre_sum[dq[-1]]:
            dq.pop()
        
        # 新元素入队
        dq.append(i)
    
    print(max_sum)

if __name__ == "__main__":
    main()

例题

问题

[洛谷 P10059 Choose][https://www.luogu.com.cn/problem/P10059]

P10059 Choose

题目背景

加强版

对于一个长度为 n 的序列 a ，定义 a 的极差表示 a 中最大值与最小值之差；定义 C(a, l, r) 表示 a 的连续子序列 [al, al + 1, …, ar]，其中 1 ≤ l ≤ r ≤ n。

题目描述

给定一个长度为 n 的序列 a。

你需要选出 a 的 k 个长度均为 L (1 ≤ L ≤ n − k + 1) 的不同连续子序列 C(a, l1, l1 + L − 1), C(a, l2, l2 + L − 1), …, C(a, lk, lk + L − 1)，其中 1 ≤ l1 < l2 < … < lk ≤ n − L + 1。

记这 k 个子序列中极差的最小值为 X，你需要求出 X 的最大值。同时，你还需要求出，在满足 X 最大的情况下 L 的最小值。

输入格式

本题有多组测试数据。

第一行一个整数 T，表示测试数据组数。

对于每组测试数据：

  • 第一行两个整数 n, k。
  • 第二行 n 个整数 a1, a2, ..., an。

输出格式

对于每组测试数据：

  • 一行两个整数 X, L，表示所求极差和子序列长度。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
3
5 1
1 2 3 4 5
5 2
1 2 3 4 5
5 3
1 2 3 4 5

输出 #1

1
2
3
4 5
3 4
2 3

输入输出样例 #2

输入 #2

1
2
3
4
5
2
5 1
1 2 2 2 3
5 2
1 2 2 2 3

输出 #2

1
2
2 5
1 2

说明/提示

【样例 1 解释】

  • k = 1 时，极差最大不超过 4，此时满足长度最短的一种方案为 [1, 2, 3, 4, 5]。
  • k = 2 时，极差最大不超过 3，此时满足长度最短的一种方案为 [1, 2, 3, 4], [2, 3, 4, 5]。
  • k = 3 时，极差最大不超过 2，此时满足长度最短的一种方案为 [1, 2, 3], [2, 3, 4], [3, 4, 5]。

【数据规模与约定】

本题采用捆绑测试。

子任务 分值 n≤ k≤ 特殊性质
1 5 105 n ai 均相等
2 5 105 1 数据随机生成
3 10 100 n 所求的 X 不超过 103
4 20 100 n 无
5 20 104 n 无
6 40 105 n 无

对于 100% 的数据，1 ≤ T ≤ 10，1 ≤ n ≤ 105，1 ≤ k ≤ n，−109 ≤ ai ≤ 109。

问题分析

首先，这道题涉及到了所谓的 极差，在选出 k 个长度均为 L 的连续子序列的同事，要求我们求这些子序列的最大值和最小值之差

对于这些子序列，我们标记其极差的最小值为 X，我们需要求出 X 的最大值个对应 L 的最小值

抽象，梳理一下

  1. 选出 k 个长度均为 L 的连续子序列
  2. 这些子序列的极差（最大值 - 最小值）的最小值为 X
  3. 求 X 的最大值，以及满足条件的最小 L

我们的目标肯定是先把 X 最大化（即在所有可能选择中，使得 k 个窗口的最小极差最大），然后在所有能达到该最大 X 的方案中，取 L 的最小值。

所以，这道题的核心是双重最大化问题：

  1. 第一目标：最大化 X（所选 k 个窗口的极差最小值）
  2. 第二目标：在满足第一目标的前提下，最小化 L（窗口长度）

从样例中可以发现规律：

  • 当 k=1 时，选最长窗口（L=5），X=4（全局极差）
  • 当 k=2 时，选次长窗口（L=4），X=3（窗口极差的最小值）
  • 当 k=3 时，选更短窗口（L=3），X=2

这是否揭示了一个重要性质，窗口长度越短，能选的窗口越多，但 X 会越小；窗口越长，X 越大，但能选的窗口越少。

其实我看题解了）））））））

首先，肯定要用到二分答案，二分查找可能的 X 值（0 .. max(a)-min(a)），对于二分出来的每个X，判断是否存在某个 L 使得能选出至少 k 个长度为 L 的窗口，且每个窗口的极差 ≤ X

然后用单调队列计算每个长度为 L 的滑动窗口的极差（最大值-最小值）

最后再判断，对于某个 X，判断是否存在长度 L 使得有至少 k 个窗口的极差 ≤ X

为了判断 是否存在某个 L，我们需要找出 最小的 L 使得窗口数量 cnt(L, X) >= k。所以也需要对 L 也二分（1..n），每次检查 cnt。

二分查找 X 的左边界就是 0，右边界就是 序列的全局极差max (a) - min (a)

对于每个 X，找最小的 L就是这篇文章的内容了

  • 用滑动窗口计算以每个位置结尾的、极差 ≤X 的最长窗口
  • 统计有多少个长度 ≥ L 的窗口可以选出 k 个不重叠的窗口

最后就是验证可行性

  • 如果存在这样的 L，说明 X 是可行的，可以尝试更大的 X
  • 否则需要减小 X

你会发现，超时了

但是，上述的分析是有必要的

观察到 X 随着 L 的减小而单调递减，因此可以：

  1. 枚举窗口长度 L：
    • 从大到小枚举 L（从 n-k+1 到 1）
    • 对于每个 L，计算所有长度为 L 的窗口的极差
    • 找出其中最小的极差 X
  2. 找到临界点：
    • 当找到第一个 L，使得有至少 k 个窗口的极差 ≥X 时，停止
    • 这个 X 就是最大可能值

至于为什么是 n-k+1，我看题解了））））https://www.luogu.com.cn/article/pvcsa357

代码

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    private static int[] a;
    private static int n, k;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());

            a = new int[n + 1];
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= n; i++) {
                a[i] = Integer.parseInt(st.nextToken());
            }
            
            // 计算最优的X
            // 选择长度为 n-k+1 的窗口，计算所有这样的窗口中极差的最小值
            int X = computeMinDiff(n - k + 1);

            // 二分查找最小的L，使得存在至少k个长度为L且极差≥X的窗口
            int left = 1, right = n - k + 1;
            int bestL = n - k + 1;

            while (left <= right) {
                int mid = left + (right - left) / 2;

                if (hasKWindowsWithDiff(mid, X)) {
                    bestL = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            sb.append(X).append(" ").append(bestL).append("\n");
        }

        System.out.print(sb);
    }

    /**
     * 计算所有长度为windowLen的窗口中，极差的最小值
     * 使用单调队列维护窗口内的最大值和最小值
     */
    private static int computeMinDiff(int windowLen) {
        Deque<Integer> maxDeque = new ArrayDeque<>();  // 维护最大值的单调递减队列
        Deque<Integer> minDeque = new ArrayDeque<>();  // 维护最小值的单调递增队列
        
        int minDiff = Integer.MAX_VALUE;

        for (int i = 1; i <= n; i++) {
            // 移除超出窗口范围的元素
            while (!maxDeque.isEmpty() && maxDeque.peekFirst() < i - windowLen + 1) {
                maxDeque.pollFirst();
            }
            while (!minDeque.isEmpty() && minDeque.peekFirst() < i - windowLen + 1) {
                minDeque.pollFirst();
            }

            // 维护单调递减队列（最大值）
            while (!maxDeque.isEmpty() && a[i] > a[maxDeque.peekLast()]) {
                maxDeque.pollLast();
            }
            maxDeque.offerLast(i);

            // 维护单调递增队列（最小值）
            while (!minDeque.isEmpty() && a[i] < a[minDeque.peekLast()]) {
                minDeque.pollLast();
            }
            minDeque.offerLast(i);

            // 当窗口形成后，计算极差
            if (i >= windowLen) {
                int maxVal = a[maxDeque.peekFirst()];
                int minVal = a[minDeque.peekFirst()];
                minDiff = Math.min(minDiff, maxVal - minVal);
            }
        }

        return minDiff;
    }

    /**
     * 检查是否存在至少k个长度为windowLen且极差≥minDiff的窗口
     */
    private static boolean hasKWindowsWithDiff(int windowLen, int minDiff) {
        Deque<Integer> maxDeque = new ArrayDeque<>();
        Deque<Integer> minDeque = new ArrayDeque<>();
        
        int count = 0;

        for (int i = 1; i <= n; i++) {
            // 移除超出窗口范围的元素
            while (!maxDeque.isEmpty() && maxDeque.peekFirst() < i - windowLen + 1) {
                maxDeque.pollFirst();
            }
            while (!minDeque.isEmpty() && minDeque.peekFirst() < i - windowLen + 1) {
                minDeque.pollFirst();
            }

            // 维护单调递减队列（最大值）
            while (!maxDeque.isEmpty() && a[i] > a[maxDeque.peekLast()]) {
                maxDeque.pollLast();
            }
            maxDeque.offerLast(i);

            // 维护单调递增队列（最小值）
            while (!minDeque.isEmpty() && a[i] < a[minDeque.peekLast()]) {
                minDeque.pollLast();
            }
            minDeque.offerLast(i);

            // 当窗口形成后，检查极差
            if (i >= windowLen) {
                int maxVal = a[maxDeque.peekFirst()];
                int minVal = a[minDeque.peekFirst()];
                
                if (maxVal - minVal >= minDiff) {
                    count++;
                    if (count >= k) {
                        return true;  // 提前退出优化
                    }
                }
            }
        }

        return count >= k;
    }

image-20251124211916148

超时了怎么办，别用现成的 Deque 了呗，自己模拟一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
import java.io.*;
import java.util.StringTokenizer;

public class Main2 {
    private static int[] a;
    private static int n, k;

    // 使用数组模拟双端队列，避免ArrayDeque的额外开销
    private static int[] maxQ, minQ;
    private static int maxHead, maxTail, minHead, minTail;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        // 预分配队列数组
        maxQ = new int[100005];
        minQ = new int[100005];

        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());

            a = new int[n + 1];
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= n; i++) {
                a[i] = Integer.parseInt(st.nextToken());
            }

            // 计算最优的X
            int X = computeMinDiff(n - k + 1);

            // 二分查找最小的L
            int left = 1, right = n - k + 1;
            int bestL = n - k + 1;

            while (left <= right) {
                int mid = (left + right) >> 1;

                if (hasKWindowsWithDiff(mid, X)) {
                    bestL = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }

            bw.write(String.valueOf(X));
            bw.write(' ');
            bw.write(String.valueOf(bestL));
            bw.write('\n');
        }

        bw.flush();
    }

    /**
     * 计算所有长度为windowLen的窗口中，极差的最小值
     */
    private static int computeMinDiff(int windowLen) {
        maxHead = maxTail = 0;
        minHead = minTail = 0;

        int minDiff = Integer.MAX_VALUE;

        for (int i = 1; i <= n; i++) {
            // 移除超出窗口范围的元素（最大值队列）
            while (maxHead < maxTail && maxQ[maxHead] < i - windowLen + 1) {
                maxHead++;
            }

            // 移除超出窗口范围的元素（最小值队列）
            while (minHead < minTail && minQ[minHead] < i - windowLen + 1) {
                minHead++;
            }

            // 维护单调递减队列（最大值）
            while (maxHead < maxTail && a[i] > a[maxQ[maxTail - 1]]) {
                maxTail--;
            }
            maxQ[maxTail++] = i;

            // 维护单调递增队列（最小值）
            while (minHead < minTail && a[i] < a[minQ[minTail - 1]]) {
                minTail--;
            }
            minQ[minTail++] = i;

            // 当窗口形成后，计算极差
            if (i >= windowLen) {
                int diff = a[maxQ[maxHead]] - a[minQ[minHead]];
                if (diff < minDiff) {
                    minDiff = diff;
                }
            }
        }

        return minDiff;
    }

    /**
     * 检查是否存在至少k个长度为windowLen且极差≥minDiff的窗口
     * 找到k个就立即返回
     */
    private static boolean hasKWindowsWithDiff(int windowLen, int minDiff) {
        maxHead = maxTail = 0;
        minHead = minTail = 0;

        int count = 0;

        for (int i = 1; i <= n; i++) {
            // 移除超出窗口范围的元素（最大值队列）
            while (maxHead < maxTail && maxQ[maxHead] < i - windowLen + 1) {
                maxHead++;
            }

            // 移除超出窗口范围的元素（最小值队列）
            while (minHead < minTail && minQ[minHead] < i - windowLen + 1) {
                minHead++;
            }

            // 维护单调递减队列（最大值）
            while (maxHead < maxTail && a[i] > a[maxQ[maxTail - 1]]) {
                maxTail--;
            }
            maxQ[maxTail++] = i;

            // 维护单调递增队列（最小值）
            while (minHead < minTail && a[i] < a[minQ[minTail - 1]]) {
                minTail--;
            }
            minQ[minTail++] = i;

            // 当窗口形成后，检查极差
            if (i >= windowLen) {
                if (a[maxQ[maxHead]] - a[minQ[minHead]] >= minDiff) {
                    count++;
                    if (count >= k) {
                        return true;  // 提前退出
                    }
                }
            }
        }

        return false;
    }
}

image-20251124212129220

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <climits>
using namespace std;

const int MAXN = 100005;
vector<int> a;
int n, k;
int maxQ[MAXN], minQ[MAXN];
int maxHead, maxTail, minHead, minTail;

// 计算所有长度为windowLen的窗口中，极差的最小值
int computeMinDiff(int windowLen) {
    maxHead = maxTail = 0;
    minHead = minTail = 0;
    
    int minDiff = INT_MAX;
    
    for (int i = 1; i <= n; i++) {
        // 移除超出窗口范围的元素（最大值队列）
        while (maxHead < maxTail && maxQ[maxHead] < i - windowLen + 1) {
            maxHead++;
        }
        
        // 移除超出窗口范围的元素（最小值队列）
        while (minHead < minTail && minQ[minHead] < i - windowLen + 1) {
            minHead++;
        }
        
        // 维护单调递减队列（最大值）
        while (maxHead < maxTail && a[i] > a[maxQ[maxTail - 1]]) {
            maxTail--;
        }
        maxQ[maxTail++] = i;
        
        // 维护单调递增队列（最小值）
        while (minHead < minTail && a[i] < a[minQ[minTail - 1]]) {
            minTail--;
        }
        minQ[minTail++] = i;
        
        // 当窗口形成后，计算极差
        if (i >= windowLen) {
            int diff = a[maxQ[maxHead]] - a[minQ[minHead]];
            if (diff < minDiff) {
                minDiff = diff;
            }
        }
    }
    
    return minDiff;
}

// 检查是否存在至少k个长度为windowLen且极差≥minDiff的窗口
bool hasKWindowsWithDiff(int windowLen, int minDiff) {
    maxHead = maxTail = 0;
    minHead = minTail = 0;
    
    int count = 0;
    
    for (int i = 1; i <= n; i++) {
        // 移除超出窗口范围的元素（最大值队列）
        while (maxHead < maxTail && maxQ[maxHead] < i - windowLen + 1) {
            maxHead++;
        }
        
        // 移除超出窗口范围的元素（最小值队列）
        while (minHead < minTail && minQ[minHead] < i - windowLen + 1) {
            minHead++;
        }
        
        // 维护单调递减队列（最大值）
        while (maxHead < maxTail && a[i] > a[maxQ[maxTail - 1]]) {
            maxTail--;
        }
        maxQ[maxTail++] = i;
        
        // 维护单调递增队列（最小值）
        while (minHead < minTail && a[i] < a[minQ[minTail - 1]]) {
            minTail--;
        }
        minQ[minTail++] = i;
        
        // 当窗口形成后，检查极差
        if (i >= windowLen) {
            if (a[maxQ[maxHead]] - a[minQ[minHead]] >= minDiff) {
                count++;
                if (count >= k) {
                    return true;  // 提前退出
                }
            }
        }
    }
    
    return false;
}

// 快速读取输入（处理大数据量）
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T = read();
    while (T--) {
        n = read();
        k = read();
        
        a.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            a[i] = read();
        }
        
        // 计算最优的X
        int X = computeMinDiff(n - k + 1);
        
        // 二分查找最小的L
        int left = 1, right = n - k + 1;
        int bestL = n - k + 1;
        
        while (left <= right) {
            int mid = (left + right) >> 1;
            
            if (hasKWindowsWithDiff(mid, X)) {
                bestL = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        cout << X << " " << bestL << "\n";
    }
    
    return 0;
}

额外说两句

这个问题使用稀疏表（Sparse Table）进行RMQ查询，代替单调队列方法，这样可以O(1)查询任意区间的最大/最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
import java.io.*;
import java.util.StringTokenizer;

public class Main {
    private static int[] a;
    private static int n, k;
    private static int[][] maxST, minST;
    private static int[] lg;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // 预处理log2值
        lg = new int[100005];
        for (int i = 2; i < 100005; i++) {
            lg[i] = lg[i / 2] + 1;
        }

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());

            a = new int[n + 1];
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= n; i++) {
                a[i] = Integer.parseInt(st.nextToken());
            }

            // 构建稀疏表（Sparse Table）用于RMQ查询
            buildSparseTable();

            // 计算最大的X：枚举k个连续窗口的所有可能位置
            int X = Integer.MAX_VALUE;
            for (int i = 1; i <= k; i++) {
                int left = i;
                int right = n - k + i;
                int maxVal = queryMax(left, right);
                int minVal = queryMin(left, right);
                X = Math.min(X, maxVal - minVal);
            }

            // 二分查找最小的L
            int leftBound = 1, rightBound = n - k + 1;
            int bestL = rightBound;

            while (leftBound <= rightBound) {
                int midL = leftBound + (rightBound - leftBound) / 2;

                if (canSelectK(midL, X)) {
                    bestL = midL;
                    rightBound = midL - 1;
                } else {
                    leftBound = midL + 1;
                }
            }

            bw.write(X + " " + bestL + "\n");
        }
        
        bw.flush();
    }

    // 构建稀疏表
    private static void buildSparseTable() {
        int logN = lg[n] + 1;
        maxST = new int[n + 1][logN];
        minST = new int[n + 1][logN];

        // 初始化
        for (int i = 1; i <= n; i++) {
            maxST[i][0] = a[i];
            minST[i][0] = a[i];
        }

        // 动态规划构建稀疏表
        for (int j = 1; j < logN; j++) {
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                maxST[i][j] = Math.max(maxST[i][j - 1], maxST[i + (1 << (j - 1))][j - 1]);
                minST[i][j] = Math.min(minST[i][j - 1], minST[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    // 查询区间最大值
    private static int queryMax(int l, int r) {
        int len = lg[r - l + 1];
        return Math.max(maxST[l][len], maxST[r - (1 << len) + 1][len]);
    }

    // 查询区间最小值
    private static int queryMin(int l, int r) {
        int len = lg[r - l + 1];
        return Math.min(minST[l][len], minST[r - (1 << len) + 1][len]);
    }

    // 判断是否可以选出k个长度为L且极差≥X的窗口
    private static boolean canSelectK(int L, int X) {
        int count = 0;
        
        for (int i = 1; i <= n - L + 1; i++) {
            int maxVal = queryMax(i, i + L - 1);
            int minVal = queryMin(i, i + L - 1);
            
            if (maxVal - minVal >= X) {
                count++;
            }
        }
        
        return count >= k;
    }
}