首页 > 试题广场 >

最大值减去最小值小于或等于num的子数组数量

[编程题]最大值减去最小值小于或等于num的子数组数量
  • 热度指数:4639 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定数组 arr 和整数 num,共返回有多少个子数组满足如下情况:
max(arr[i...j]) - min(arr[i...j]) <= num
max(arr[i...j])表示子数组arr[i...j]中的最大值,min[arr[i...j])表示子数组arr[i...j]中的最小值。


输入描述:
第一行输入两个数 n 和 num,其中 n 表示数组 arr 的长度
第二行输入n个整数X_i,表示数组arr中的每个元素


输出描述:
输出给定数组中满足条件的子数组个数
示例1

输入

5 2 
1 2 3 4 5

输出

12

备注:


//详情请见左神书籍,这个算法碉堡了
//我针对一些代码写些注释方便理解
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
int main()
{
	long long n; long long num;
	cin >> n >> num;
	vector<long long> datas(n, 0);
	for (int i = 0; i<n; i++)
	{
		long long x;
		cin >> x;
		datas[i] = x;
	}
        //以上用于输入
	deque<int> dq1;//最大值队列
	deque<int> dq2;//最小值队列
	int res = 0;
	int j = 0;
	int i = 0;
	for (; i<datas.size(); i++)
	{ //以i为起始位置的子数组
            for (; j<datas.size(); j++)
		{
			while (!dq1.empty() && datas[j] >= datas[dq1.back()])
				dq1.pop_back();
			dq1.push_back(j);
			while (!dq2.empty() && datas[j] <= datas[dq2.back()])
				dq2.pop_back();
			dq2.push_back(j);
                        //如果最大值减去最小值大于num就break,此时最大值
                        //减去最小值大于num一定是由于j的插入
			if (datas[dq1.front()] - datas[dq2.front()]>num)
				break;
		}
		if (dq1.front() == i)//如果队头是i位置的元素,i加一后就过期删掉
			dq1.pop_front();
		if (dq2.front() == i)
			dq2.pop_front();
		res += j - i;//以i为开头的小于num的子数组长度j-i
	}
	cout <<res <<endl;
}

编辑于 2019-08-19 10:41:45 回复(1)

自己实现的时候注意使用下标比较还是使用值在比较,不要搞混。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int num = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int res = getArrayNum(arr, num);
        System.out.println(res);
    }

    //两个结论:1.到j不满足条件,a[i..j-1]满足条件所以a[m..n]都满足条件(i<=m<=n<=j-1)
    //2.a[i..j]不满足条件,则包含它的也都不满足条件(a[l..k],l<=i<=j<=k)
    //用a[i..j-1]代入条件:max(a[i..j])-min(a[i..j])<=num里进行归纳

    public static int getArrayNum(int[] arr, int num) {
        //判空
        if(arr == null || arr.length == 0){
            return 0;
        }
        //拿LinkedList作为双端队列来使用
        LinkedList qmax = new LinkedList();
        LinkedList qmin = new LinkedList();
        //j是不重置的,因为上面两个结论,到j不满足条件时,j是不变的,所以j只会不断地增长
        //j不重置则使用while语句
        int i = 0;
        int j = 0;
        int result = 0;
        //到j不满足条件时,i..j-1所有的子数组都满足条件,但是计数的时候只计算了从i开头的
        //后面剩下的会到它们为开头的时候计算(如i+1),这也是j不重置的原因
        while(i < arr.length){
            while(j < arr.length){
                //为了保证同一个下标只进栈一次,出栈一次,这样时间复杂度才能保证(每个元素O(1),n个元素O(n))
                //如果break,j不变,而qmin.peekLast()正好是上一轮的j,后面i++,所以判断[i+1..j]是否满足条件
                //到j不满足条件,所以[i+1..j]不一定满足条件
                if(qmin.isEmpty() || qmin.peekLast() != j){
                    //双端队列结构
                    while(!qmax.isEmpty() && arr[j] >= arr[qmax.peekLast()]){
                        qmax.pollLast();
                    }
                    qmax.addLast(j);
                    while(!qmin.isEmpty() && arr[j] <= arr[qmin.peekLast()]){
                        qmin.pollLast();
                    }
                    qmin.addLast(j);
                }
                if(arr[qmax.peekFirst()] - arr[qmin.peekFirst()] > num){
                    break;
                }
                j++;
            }
            //以i开头一共j-i个,a[i..i]到a[i..j-1]
            result += (j - i);
            //开头i要自增,应该把队列中的i移除,只可能在最大和最小地方出现,要不就提前被弹出了
            if(qmax.peekFirst() == i){
                qmax.pollFirst();
            }
            if(qmin.peekFirst() == i){
                qmin.pollFirst();
            }
            i++;
        }
        return result;
    }
}
发表于 2020-09-10 16:55:02 回复(0)
和滑动窗口那题类似,都是找当前窗口内最大/最小值
import java.util.LinkedList;
import java.util.Scanner;

public class Main {

    public static int getNum(int[] arr, int num) {
        if (arr == null || arr.length == 0) return 0;
        LinkedList<Integer> qmin = new LinkedList<>();
        LinkedList<Integer> qmax = new LinkedList<>();
        int i = 0, j = 0, res = 0;
        while (i < arr.length) {
            // 求以arr[i]为开头,满足条件最长的子序列
            while (j < arr.length) {
                if (qmin.isEmpty() || qmin.peekLast() != j) {
                    while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[j]) {
                        qmin.pollLast();
                    }
                    qmin.addLast(j);
                    while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[j]) {
                        qmax.pollLast();
                    }
                    qmax.addLast(j);
                }
                // 当不再满足题意,max(arr[i...j] - min(arr[i...j]) <= num 退出当前循环
                if (arr[qmax.getFirst()] - arr[qmin.getFirst()] > num)
                    break;
                j++;
            }
            // 以arr[i]为第一个元素的子数组,满足条件的j-i个
            res += j - i;
            // 下一次从i+1开始,删除队列里不再框内的元素arr[i]
            if (qmin.peekFirst() == i) qmin.pollFirst();
            if (qmax.peekFirst() == i) qmax.pollFirst();
            i++;
        }
        return res;
    }


    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int num = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int res = getNum(arr, num);
        System.out.println(res);
    }
}


编辑于 2020-06-14 13:43:31 回复(1)
双队列qmin, qmax,相当于两个最大滑动窗口,保证qmin, qmax 队首为最小值和最大值;
#include<bits/stdc++.h>
using namespace std;

int getNum(vector<int>& arr, int num)
{
    int n = arr.size();
    deque<int> qmin, qmax;
    int i=0, j=0, res=0; 
    while(i<n) {
        while(j<n) {
            while(!qmin.empty() && arr[qmin.back()]>=arr[j]) {
                qmin.pop_back();
            }
            qmin.push_back(j);
            
            while(!qmax.empty() && arr[qmax.back()]<=arr[j])
            {
                qmax.pop_back();
            }
            qmax.push_back(j);
            
            if(arr[qmax.front()] - arr[qmin.front()] > num) break;
            j++;
        }
        if(qmin.front()==i) qmin.pop_front();
        if(qmax.front()==i) qmax.pop_front();
        res += j - i;
        i++;
    }
    return res;
}

int main()
{
    int n, num;
    cin>>n>>num;
    vector<int> arr(n, 0);
    for(int i=0; i<n; i++)
    {
        cin>>arr[i];
    }
    cout<< getNum(arr, num);
    return 0;
}


发表于 2020-05-11 18:32:10 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m;
    cin>>n>>m;
    int a[n], cnt=n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0,j=1,l=0,r=0, Max, Min;i<n-1;i++){
        if(l<=i || r<=i){
            Max = Min = a[i];
            l = r = i;
            for(j=i+1;j<n;j++){
                if(a[j]>Max){
                    Max = a[j];
                    l = j;
                }
                if(a[j]<Min){
                    Min = a[j];
                    r = j;
                }
                if(Max-Min>m)
                    break;
            }
        }
        cnt += j-i-1;
    }
    cout<<cnt<<endl;
    return 0;
}

发表于 2020-02-12 03:12:33 回复(0)
// golang 版本的,用 gods 库提供的双链表
import (    "fmt"  dll "github.com/emirpasic/gods/lists/doublylinkedlist" ) 


func getArrayNum(nums []int, k int) int { qMax := dll.New() qMin := dll.New() res := 0 i, j := 0, 0 for ; i < len(nums); i++ { for j < len(nums) { preMax, _ := qMax.Get(qMax.Size() - 1) for qMax.Size() > 0 && nums[preMax.(int)] <= nums[j] { qMax.Remove(qMax.Size() - 1) preMax, _ = qMax.Get(qMax.Size() - 1) } qMax.Append(j) preMin, _ := qMin.Get(qMin.Size() - 1) for qMin.Size() > 0 && nums[preMin.(int)] >= nums[j] { qMin.Remove(qMin.Size() - 1) preMin, _ = qMin.Get(qMin.Size() - 1) } qMin.Append(j) preMax, _ = qMax.Get(0) preMin, _ = qMin.Get(0) if nums[preMax.(int)]-nums[preMin.(int)] > k { break } j++ } qq, _ := qMin.Get(0) mm, _ := qMax.Get(0) if qq.(int) == i { qMin.Remove(0) } if mm.(int) == i { qMax.Remove(0) } res += j - i } return res }

发表于 2024-01-23 15:10:32 回复(0)
一毛一样的思路,为什么 golang 超时了呢?

package main

import (
	"fmt"
)

/**
窗口内最大值或最小值更新结构的实现
假设一个固定大小为W的窗口,依次划过arr,
返回每一次滑出状况的最大值
例如,arr = [4,3,5,4,3,3,6,7], W = 3
返回:[5,5,5,4,6,7]
*/

func maxSlidingWindow(nums []int, k int) []int {
	r := 0
	res := []int{}
	queue := []int{}
	for r < len(nums) {
		//当前元素大于等于队列尾部元素,弹出队尾元素, 直到队列为空或者队尾元素大于当前元素
		for len(queue) != 0 && nums[r] >= nums[queue[len(queue)-1]] {
			queue = queue[:len(queue)-1]
		}
		//加入队尾, 队列中存放的是索引
		queue = append(queue, r)
		for r-k+1 > queue[0] {
			queue = queue[1:]
		}

		//前 k - 1 个数不用加入结果
		if r >= k-1 {
			res = append(res, nums[queue[0]])
		}
		r++
	}
	return res
}

/**
给定一个整型数组arr,和一个整数num
某个arr中的子数组sub,如果想达标,必须满足:sub中最大值 – sub中最小值 <= num,
返回arr中达标子数组的数量

5 2
1 2 3 4 5
*/

func countSubArray(arr []int, num int) int {
	if len(arr) == 0 {
		return 0
	}
	ans := 0
	l, r := 0, 0
	minW, maxW := []int{}, []int{}
	for l < len(arr) {
		// r 往右扩, 遇到第一个不达标的停止
		// 计算以 l 开始的子数组个数
		for r < len(arr) {
			for len(maxW) != 0 && arr[maxW[len(maxW)-1]] <= arr[r] {
				maxW = maxW[:len(maxW)-1]
			}
			maxW = append(maxW, r)

			for len(minW) != 0 && arr[minW[len(minW)-1]] >= arr[r] {
				minW = minW[:len(minW)-1]
			}
			minW = append(minW, r)

			if arr[maxW[0]]-arr[minW[0]] <= num {
				r++
			} else {
				break
			}
		}

		for len(maxW) > 0 && maxW[0] <= l {
			maxW = maxW[1:]
		}
		for len(minW) > 0 && minW[0] <= l {
			minW = minW[1:]
		}

		ans += r - l

		l++
	}

	return ans
}

func main() {
	var n, num int
	fmt.Scan(&n, &num)
	
	arr := []int{}
	for i := 1; i <= n; i++ {
		var t int
		if cc, _ := fmt.Scan(&t); cc == 0 {
			break
		}
		arr = append(arr, t)
	}


	count := countSubArray(arr, num)
	fmt.Println(count)
}


发表于 2022-10-08 10:44:52 回复(0)
用两个单调deque,分别存储滑动窗口中的最大值和最小值
代码如下:
#include "bits/stdc++.h"

/*
方法1:复杂度O(n*n)
方法2:即用双向单调队列求窗口最大值和最小值
*/

using namespace std;
int main()
{
    int len;cin>>len;
    int num;cin>>num;
    int ret=0;
    vector<int> vec(len);
    for(int i=0;i<len;i++)cin>>vec[i];
    /*for(int i=0;i<len;i++)
    {
        int max_num=vec[i];
        int min_num=vec[i];
        for(int j=i;j<len;j++)
        {
            max_num=max(max_num,vec[j]);
            min_num=min(min_num,vec[j]);
            if(max_num-min_num<=num) ret++;
            else break;
        }
    }*/
    deque<int> stk_max;
    deque<int> stk_min;
    //int flag=1;
    int i=0,j=0;
    while(i<len)
    {
        while(j<len)
        {
            if(stk_min.empty()||stk_min.back()!=vec[j])
            {
                while(!stk_max.empty()&&stk_max.back()<vec[j]){stk_max.pop_back();}
                stk_max.push_back(vec[j]);
                while(!stk_min.empty()&&stk_min.back()>vec[j]){stk_min.pop_back();}
                stk_min.push_back(vec[j]);
            }
            //else if()
            if(stk_max.front()-stk_min.front()>num) {break;}
            j++;//flag=1;
            //cout<<j<<' ';
        }
        if(stk_max.front()==vec[i])stk_max.pop_front();
        if(stk_min.front()==vec[i])stk_min.pop_front();
        ret+=j-i;//表示,以i开头的子数组
        i++;
        //flag=0;
        //cout<<j<<' '<<i<<' '<<ret<<endl;
    }
    cout<<ret;
    return 0;
}


发表于 2022-02-13 15:05:02 回复(0)
这题目真是一点都不严谨,也不说一下子数组是连续的,害得我想半天,还想着先排个序,然后滑动窗口计算各种组合值。。
从小到大都做过那么多数学题,[i..j]就连续了吗,起码写[i,i+1,i+2,…,j],写[i..j]我怎么知道中间没有跳跃呢
发表于 2021-11-05 11:27:59 回复(1)
#include <bits/stdc++.h>

using namespace std;

int main(){
    int n, num;
    scanf("%d%d", &n, &num);
    vector<int> v(n, 0);
    for(int i = 0; i < n; i++)
        scanf("%d", &v[i]);
    
    deque<int> qmax, qmin;
    int res = 0;
    
    int i = 0, j = 0;
    
    qmax.push_back(0);
    qmin.push_back(0);
    
    while(i < n){
        while(j < n && v[qmax.front()] - v[qmin.front()] <= num){
            j++;
            while(!qmax.empty() && v[qmax.back()] < v[j])
                qmax.pop_back();
            qmax.push_back(j);
            
            while(!qmin.empty() && v[qmin.back()] > v[j])
                qmin.pop_back();
            qmin.push_back(j);
        }
        
        res += j - i;
        
        i++;
        
        if(qmax.front() < i)
            qmax.pop_front();
        
        if(qmin.front() < i)
            qmin.pop_front();
    }
    
    printf("%d\n", res);
    return 0;
} 

发表于 2021-08-26 23:20:09 回复(0)

今天吃火龙果

let qmax=[],qmin=[]
let i=0,j=0
while(j<line.length&&i<line.length){ 
    // j一定是极值进栈才会i右移
    //如果极值进栈则先处理前面的 先不让极值进栈
    while(qmin.length>0&&qmax.length>0&&((line[j]<line[qmin[0]]&&line[qmax[0]]-line[j]>n)
    ||(line[j]>line[qmax[0]]&&line[j]-line[qmin[0]]>n))){
        res+=j-i
        if(qmin[0]==i)qmin.shift()      
        if(qmax[0]==i) qmax.shift()
        i++
    }
    while(qmin.length>0 && line[qmin[qmin.length-1]]>line[j]) qmin.pop()         
    qmin.push(j)
    while(qmax.length>0 && line[qmax[qmax.length-1]]<line[j]) qmax.pop()
    qmax.push(j)  
    j++

}

// j到最后一个了
while(qmin.length>0&&qmax.length>0&&line[qmax[0]]-line[qmin[0]]<=n){
    res+=j-i
    if(qmin[0]==i)qmin.shift()      
    if(qmax[0]==i)qmax.shift()
    i++
}

console.log(res)
发表于 2021-06-29 13:52:25 回复(0)
import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(new BufferedInputStream(System.in));
        int n=sc.nextInt();
        int num=sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        
        int[] min=new int[n];
        int[] max=new int[n];
        int minl=0;
        int minr=-1;
        int maxl=0;
        int maxr=-1;
        int i=0;
        int j=0;
        int res=0;
        while(i<n){
            while(j<n){ 
                while(minl<=minr&&arr[min[minr]]>=arr[j]) minr--;
                min[++minr]=j;
                while(maxl<=maxr&&arr[max[maxr]]<=arr[j]) maxr--;
                max[++maxr]=j;
                if(-arr[min[minl]]+arr[max[maxl]]>num){
                    break;
                }
                j++;
            }
            res+=j-i;
            if(max[maxl]==i) maxl++;
            if(min[minl]==i) minl++;
            i++;
        }
        System.out.println(res);
    }
}

发表于 2020-08-30 21:15:05 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int num = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int res = getArrayNum(arr, num);
        System.out.println(res);
    }
    
    public static int getArrayNum(int[] arr, int num) {
        if(arr == null || arr.length == 0)
            return 0;
        LinkedList<Integer> qmax = new LinkedList<>();
        LinkedList<Integer> qmin = new LinkedList<>();
        int res = 0;
        int L = 0;
        int R = 0;
        while(L < arr.length) {
            while(R < arr.length) {
                while(!qmax.isEmpty() && arr[qmax.getLast()] <= arr[R])
                    qmax.removeLast();
                qmax.add(R);
                while(!qmin.isEmpty() && arr[qmin.getLast()] >= arr[R])
                    qmin.removeLast();
                qmin.add(R);
                if(arr[qmax.getFirst()] - arr[qmin.getFirst()] > num)
                    break;
                R++;
            }
            res += R - L;
            if(qmax.getFirst() == L)
                qmax.removeFirst();
            if(qmin.getFirst() == L)
                qmin.removeFirst();
            L++;
        }
        return res;
    }
}

发表于 2020-08-19 14:09:01 回复(0)

C++抄书方法

自己按照书上思路写了一下,发现写得比书上复杂
于是乎,还是用的书上
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, num;
    cin>>n>>num;
    vector<int> v(n);
    for(int i=0;i<n;i++)
        cin>>v[i];
    deque<int> dq_max;
    deque<int> dq_min;
    int i=0, j=0, res=0;
    while(i < n){
        while(j < n){
            if(dq_min.empty() || dq_min.back()!=j){
                while(dq_min.empty()==false && v[dq_min.back()]>v[j])
                    dq_min.pop_back();
                dq_min.push_back(j);
                while(dq_max.empty()==false && v[dq_max.back()]<v[j])
                    dq_max.pop_back();
                dq_max.push_back(j);
            }
            if(v[dq_max.front()] - v[dq_min.front()] > num)
                break;
            ++j;
        }
        res += j-i;
        if(dq_max.front() == i)
            dq_max.pop_front();
        if(dq_min.front() == i)
            dq_min.pop_front();
        ++i;
    }
    cout<<res;
    return 0;
}


发表于 2020-08-04 20:53:50 回复(0)
arrnum,num=map(int,input().split())
arr=list(map(int,input().split()))
n=0
for i in range(len(arr)):
    for j in range(i+1,len(arr)+1):
        if max(arr[i:j])-min(arr[i:j]) <=num:
            n+=1
print(n)
发表于 2020-03-04 07:14:12 回复(0)
表示没看过书,暴力解法而已。
import java.util.*;
 
public class Main{
 
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            int num = in.nextInt();
            int[] arr = new int[n];
            for(int i=0;i<n;i++){
                arr[i] = in.nextInt();
            }
            int sum = 0;
            //包含arr[i]且符合条件的的子数组个数
            for(int i=0;i<n;i++){
                sum++;
                int min = arr[i],max = arr[i];
                int j=i;
                while(j<n-1){
                    int next = arr[j+1];
                    if(max < next && next-min <= num){
                        max = next;
                        j++;
                        sum++;
                    }
                    else if(min > next && max-next <= num){
                        min = next;
                        j++;
                        sum++;
                    }
                    else if( min<=next && next<=max && max - min <= num){
                        j++;
                        sum++;
                    }
                    else break;
                }
                
            }
            System.out.println(sum);
        }
    }
}

发表于 2020-01-17 22:29:41 回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class Main {
/**
     * 利用两个双端队列来实现子数组最大值和最小值的更新
     */
    public static int getNum(int[] arr, int num) {
        // 排除三种特例:null 空数组[] num小于0
        if (arr == null || arr.length < 1 || num < 0) {
            return -1;
        }
        // 初始化子数组的最大值候选数组的下标
        LinkedList<Integer> qmax = new LinkedList<>();
        // 初始化子数组的最小值候选数字的下标
        LinkedList<Integer> qmin = new LinkedList<>();
        int res = 0;
        int i = 0;
        int j = 0;
        // 求以arr[i]开头的子数组中有多少个满足条件的
        while (i < arr.length) {
            while (j < arr.length) {
                // 更新j++后的最大值和最小值
                while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[j]) {
                    qmax.pollLast();
                }
                qmax.addLast(j);
                while (!qmin.isEmpty() && arr[qmin.peekLast()] >= arr[j]) {
                    qmin.pollLast();
                }
                qmin.addLast(j);
                if (arr[qmax.peekFirst()] - arr[qmin.peekFirst()] > num) {
                    // [i,j]不满足条件,则[i,j+1]...[i,arr.length-1]均不满足条件
                    break;
                }
                j++;
            }
            // [i,i]...[i,j-1]均满足条件,共有j-1-i+1个
            res += j - i;
            // 更新i++后的最大值和最小值
            if (qmax.peekFirst() == i) {
                qmax.pollFirst();
            }
            if (qmin.peekFirst() == i) {
                qmin.pollFirst();
            }
            i++;
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] numbers = bufferedReader.readLine().split(" ");
        int n = Integer.valueOf(numbers[0]);
        int num = Integer.valueOf(numbers[1]);
        int[] arr = new int[n];
        numbers = bufferedReader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.valueOf(numbers[i]);
        }
        System.out.println(getNum(arr, num));
    }
}

发表于 2019-12-15 21:09:35 回复(0)