思路:双指针

使用滑动窗口维护当前区间的最大值和最小值，通过双端队列高效更新。当新增元素导致最大值与最小值的差超过k时，当前区间作为一个分组，分组数增加，并从当前元素重新开始新的窗口。这样确保分组数最少。

代码

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 读取n和k
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        long k = Long.parseLong(st.nextToken());
        
        // 读取数组a
        long[] a = new long[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++) {
            a[i] = Long.parseLong(st.nextToken());
        }
        
        System.out.println(minGroups(n, k, a));
    }
    
    // 计算最少分组数
    public static int minGroups(int n, long k, long[] a) {
        Deque<Integer> maxdq = new ArrayDeque<>(); // 维护当前窗口的最大值
        Deque<Integer> mindq = new ArrayDeque<>(); // 维护当前窗口的最小值
        int groups = 1; // 初始化分组数
        int left = 0;   // 窗口左边界
        
        for(int right=0; right<n; right++) {
            // 更新最大值队列
            while(!maxdq.isEmpty() && a[right] > a[maxdq.peekLast()]) {
                maxdq.pollLast();
            }
            maxdq.offerLast(right);
            
            // 更新最小值队列
            while(!mindq.isEmpty() && a[right] < a[mindq.peekLast()]) {
                mindq.pollLast();
            }
            mindq.offerLast(right);
            
            // 如果当前窗口不满足条件，分组并重置窗口
            if(a[maxdq.peekFirst()] - a[mindq.peekFirst()] > k) {
                groups++;
                left = right;
                
                // 清空队列并加入当前元素
                maxdq.clear();
                mindq.clear();
                maxdq.offerLast(right);
                mindq.offerLast(right);
            }
        }
        
        return groups;
    }
}

python

# 读取输入
n, k = map(int, input().split())
a = list(map(int, input().split()))

from collections import deque

def min_groups(n, k, a):
    maxdq = deque()  # 用于维护当前窗口的最大值
    mindq = deque()  # 用于维护当前窗口的最小值
    groups = 1       # 初始化分组数
    left = 0         # 窗口左边界

    for right in range(n):
        # 更新最大值队列
        while maxdq and a[right] > a[maxdq[-1]]:
            maxdq.pop()
        maxdq.append(right)
        
        # 更新最小值队列
        while mindq and a[right] < a[mindq[-1]]:
            mindq.pop()
        mindq.append(right)
        
        # 如果当前窗口不满足条件，分组并重置窗口
        if a[maxdq[0]] - a[mindq[0]] > k:
            groups += 1
            left = right  # 新分组从当前元素开始
            
            # 清除之前的队列
            maxdq.clear()
            mindq.clear()
            maxdq.append(right)
            mindq.append(right)
    
    return groups

print(min_groups(n, k, a))

cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    ll k;
    cin >> n >> k;
    vector<ll> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    
    // 双端队列维护最大值和最小值的索引
    deque<int> maxdq;
    deque<int> mindq;
    int groups = 1; // 初始化分组数
    int left = 0; // 窗口左边界
    
    for(int right=0; right<n; right++){
        // 更新最大值队列
        while(!maxdq.empty() && a[right] > a[maxdq.back()]){
            maxdq.pop_back();
        }
        maxdq.push_back(right);
        
        // 更新最小值队列
        while(!mindq.empty() && a[right] < a[mindq.back()]){
            mindq.pop_back();
        }
        mindq.push_back(right);
        
        // 如果当前窗口不满足条件，分组并重置窗口
        if(a[maxdq.front()] - a[mindq.front()] > k){
            groups++;
            left = right;
            
            // 清空队列并加入当前元素
            maxdq.clear();
            mindq.clear();
            maxdq.push_back(right);
            mindq.push_back(right);
        }
    }
    
    cout << groups;
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

有$n$个物品，第$i$个物品的价值为$a_i$。

现在要给这些物品分组，每一组必须是一个下标连续的区间。

同时，每一组内的物品差距不能太大，即任意一组内物品的最大价值减去最小价值不能超过某个给定的常数$k$。

给定这些物品，请问最少要分几组?

输入描述

第一行两个整数 $n,k(1 ≤n≤ 10^5 ,0 ≤k≤ 10^9)$，表示物品的数量及给定的常数。

第二行$n$个整数 $a (0 ≤ a_i ≤ 10^9)$，表示物品的价值。

输出描述

输出一行一个整数，表示最少的分组数。

样例1

输入

4 1
1 3 1 4

输出

4

说明

样例2

输入

4 2
1 3 1 4

输出

2

说明