题解 | #差距管理#

题目链接

思路分析

1. 问题定性与贪心策略

本题要求将一个连续的数组划分为最少的几个连续子数组（组），使得每个子数组内的最大值与最小值的差不超过一个给定的常数 $k$ 。

这是一个最优化问题，通常可以考虑动态规划或贪心算法。对于这类“最少划分”问题，一个常见的思路是尝试贪心。

我们可以制定一个贪心策略：对于每一个新开始的组，我们都尽可能地让它包含更多的元素。也就是说，从一个起始位置 $i$ 开始，我们不断向右扩展区间的右端点 $j$ ，直到区间 $[i, j]$ 首次不满足 max(a[i...j]) - min(a[i...j]) <= k 的条件为止。此时，我们就找到了从 $i$ 出发的最长有效分组，即 $[i, j-1]$ 。然后，我们从位置 $j$ 开始，重复这个过程，寻找下一个最长的有效分组。

这个贪心策略是正确的。因为通过让当前分组尽可能长，我们使得下一个分组的起始点尽可能靠右。这确保了我们总是以最“节约”的方式使用数组元素，从而使得总的分组数量最少。

2. 算法实现与优化

确定了贪心策略后，问题就变成了如何高效地实现它。一个朴素的实现方式是：

groups = 0
i = 0
while i < n:
  groups += 1
  max_val = -inf, min_val = +inf
  j = i
  while j < n:
    max_val = max(max_val, a[j])
    min_val = min(min_val, a[j])
    if max_val - min_val > k:
      break
    j += 1
  i = j

这种实现方式中，外层循环的指针 i 不断向前推进，但内层循环的指针 j 每次都从 i 开始。总的时间复杂度是 $O(N^2)$ ，对于 $N=2 \times 10^5$ 的数据规模来说会超时。

我们需要优化“寻找最长有效分组”这一过程。当我们从一个固定的起点 i 向右移动终点 j 时，我们实际上是在维护一个滑动窗口 $[i, j]$ 的最大值和最小值。这是一个经典的滑动窗口最值问题，可以使用**单调双端队列（Monotonic Deque）**来解决。

我们可以使用两个双端队列，一个 max_dq 维护窗口内递减的元素（的索引），队首总是当前窗口最大值；另一个 min_dq 维护窗口内递增的元素（的索引），队首总是当前窗口最小值。

3. 最终算法流程

结合贪心策略和单调队列优化，我们可以得到一个 $O(N)$ 的算法：

初始化分组数 groups = 0，数组的当前处理位置 i = 0。
当 i 还未越界时，循环： a. 分组数 groups 加一，表示我们开始了一个新的分组。 b. 初始化一个空的 max_dq 和 min_dq。 c. 设置当前组的右边界探索指针 j = i。 d. 当 j 还未越界时，循环： i. 将当前元素 a[j] 加入 max_dq 和 min_dq，同时维护它们的单调性。 ii. 取出队首元素得到当前窗口 $[i, j]$ 的最大值 max_val 和最小值 min_val。 iii. 如果 max_val - min_val > k，说明加入 a[j] 后窗口不再有效。最长的有效分组是 $[i, j-1]$ 。跳出内层循环。 iv. 否则，窗口 $[i, j]$ 仍然有效，继续探索，j 加一。 e. 将下一个分组的起始位置更新为 i = j。
循环结束后，groups 即为最少分组数。

整个过程中，i 和 j 指针都只会从左到右遍历数组一次，每个元素也最多进出单调队列一次，因此总的时间复杂度是 $O(N)$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

void solve() {
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    int groups = 0;
    int i = 0;
    while (i < n) {
        groups++;
        deque<int> max_dq, min_dq;
        int j = i;
        while (j < n) {
            // 维护最大值单调队列 (队首到队尾单调递减)
            while (!max_dq.empty() && a[max_dq.back()] <= a[j]) {
                max_dq.pop_back();
            }
            max_dq.push_back(j);

            // 维护最小值单调队列 (队首到队尾单调递增)
            while (!min_dq.empty() && a[min_dq.back()] >= a[j]) {
                min_dq.pop_back();
            }
            min_dq.push_back(j);

            // 检查当前窗口是否有效
            if (a[max_dq.front()] - a[min_dq.front()] > k) {
                break; // a[j] 无法被包含在当前组
            }
            j++;
        }
        i = j; // 从 j 开始下一个新组
    }
    cout << groups << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        int groups = 0;
        int i = 0;
        while (i < n) {
            groups++;
            Deque<Integer> maxDq = new ArrayDeque<>();
            Deque<Integer> minDq = new ArrayDeque<>();
            int j = i;
            while (j < n) {
                // 维护最大值单调队列
                while (!maxDq.isEmpty() && a[maxDq.peekLast()] <= a[j]) {
                    maxDq.pollLast();
                }
                maxDq.addLast(j);
                
                // 维护最小值单调队列
                while (!minDq.isEmpty() && a[minDq.peekLast()] >= a[j]) {
                    minDq.pollLast();
                }
                minDq.addLast(j);
                
                if (a[maxDq.peekFirst()] - a[minDq.peekFirst()] > k) {
                    break;
                }
                j++;
            }
            i = j;
        }
        System.out.println(groups);
    }
}

import sys
from collections import deque

def solve():
    try:
        n, k = map(int, sys.stdin.readline().split())
        a = list(map(int, sys.stdin.readline().split()))
    except (IOError, ValueError):
        return

    groups = 0
    i = 0
    while i < n:
        groups += 1
        max_dq = deque()
        min_dq = deque()
        j = i
        while j < n:
            # 维护最大值单调队列
            while max_dq and a[max_dq[-1]] <= a[j]:
                max_dq.pop()
            max_dq.append(j)
            
            # 维护最小值单调队列
            while min_dq and a[min_dq[-1]] >= a[j]:
                min_dq.pop()
            min_dq.append(j)
            
            if a[max_dq[0]] - a[min_dq[0]] > k:
                break
            j += 1
        i = j
    print(groups)

solve()

算法及复杂度

算法：贪心 + 双指针 + 单调队列
时间复杂度： $O(N)$ 。外层循环的指针 i 和内层循环的指针 j 都只会从头到尾遍历数组一次。每个数组元素的索引最多被压入和弹出单调队列各一次，均摊复杂度为 $O(1)$ 。
空间复杂度： $O(N)$ 。在最坏的情况下（例如数组完全单调），双端队列中可能需要存储所有元素的索引。