子数组的取值范围-贪心算法

互联网 2021/4/9 1:25:13

Description 给定数组arr和整数num,求arr的连续子数组中满足:其最大值减去最小值的结果大于num的个数。请实现一个时间复杂度为O(length(arr))的算法。 Input 输入第一行为测试用例个数。每一个用例有若干行,第一行为数组,每一个数用空格隔开,第二行为num。 Output 输…
Description 给定数组arr和整数num,求arr的连续子数组中满足:其最大值减去最小值的结果大于num的个数。请实现一个时间复杂度为O(length(arr))的算法。 Input 输入第一行为测试用例个数。每一个用例有若干行,第一行为数组,每一个数用空格隔开,第二行为num。 Output 输出一个值。 Sample Input 1  1 3 6 4 3 2 2 Sample Output 1 6   解题思路: 最暴力方法可以找所有的子数组,然后判断差值是否超过num。 对于以i为起始点的子数组,如果(i-j)为存在差值超过num的最小范围,那么j之后的元素加到后面也一定满足条件。也就是数量为arr.size-j。 暴力方法可以遍历数组元素i,找到差值超过num的最小范围(i-j)。时间复杂度为O(n^2)。 要达到更小时间复杂度,可以使用双端队列。qmax和qmin存储以i为起始的子数组最大值和最小值。 算法步骤如下: 1.定义左指针l和右指针r,初始指向第一个元素,并将第一个元素加入qmax和qmin队列。 2.右指针右移一位,将右指针指向元素temp插入qmax和qmin尾部。对于qmax,如果尾部有元素比temp更小,则弹出;对于qmin,如果尾部有元素比temp更大,则弹出。 3.判断qmax和qmin首元素差值是否超过num。   超过则说明该窗口(l-r)达到满足条件的最小范围的以l起始的子数组,计算出size-r,然后将l指针右移动一位,同时判断qmax和qmin首元素是否是去除元素,是的话也要弹出。然后返回步骤3继续判断。   不超过的话则返回步骤2,直到r指针移动到数组末尾。   代码如下:
 1 import java.util.*;
 2 
 3 public class Main { // 注意类名必须为Main
 4     public static void main(String[] args) {
 5         Scanner scan = new Scanner(System.in);
 6         int number = Integer.parseInt(scan.nextLine());
 7         // number个测试样例
 8         for (int k = 0; k < number; k++){
 9             // 输入数据
10             String str = scan.nextLine();
11             int num = Integer.parseInt(scan.nextLine());
12             String[] strs = str.split(" ");
13             int n = strs.length;
14             int[] arr = new int[n];
15             for (int i = 0; i < n; i++)
16                 arr[i] = Integer.parseInt(strs[i]);
17             // 特殊情况,num<0,所有子数组都满足条件
18             if (num < 0) {
19                 System.out.println(n*(n+1)/2);
20             } else {
21                 int sum = 0;
22                 // 两个双端队列,存储窗口内最大值和最小值
23                 LinkedList<Integer> qmax = new LinkedList<>();
24                 LinkedList<Integer> qmin = new LinkedList<>();
25                 int l = 0;
26                 int r;
27                 for (r = 0; r < n; r++) {
28                     // 将第r个元素插入qmax
29                     while (!qmax.isEmpty() && arr[r] > arr[qmax.getLast()])
30                         qmax.pollLast();
31                     qmax.addLast(r);
32                     // 将第r个元素插入qmin
33                     while (!qmin.isEmpty() && arr[r] < arr[qmin.getLast()])
34                         qmin.pollLast();
35                     qmin.addLast(r);
36                     // 如果差值超过num
37                     if (arr[qmax.getFirst()] - arr[qmin.getFirst()] > num) {
38                         // 计算个数
39                         sum += n-r;
40                         // 将指针l指向的元素去除
41                         if (l == qmax.getFirst())
42                             qmax.pollFirst();
43                         if (l == qmin.getFirst())
44                             qmin.pollFirst();
45                         // 左指针右移一格
46                         l++;
47                         // 右指针暂时保持不动
48                         r--;
49                     }
50                 }
51                 System.out.println(sum);
52             }
53         }
54         scan.close();
55     }
56 
57 }

 

随时随地学软件编程-关注百度小程序和微信小程序
关于找一找教程网

本站文章仅代表作者观点,不代表本站立场,所有文章非营利性免费分享。
本站提供了软件编程、网站开发技术、服务器运维、人工智能等等IT技术文章,希望广大程序员努力学习,让我们用科技改变世界。
[子数组的取值范围-贪心算法]http://www.zyiz.net/tech/detail-154080.html

上一篇:算法题:字符串s1,s2,判断s1的任意排列是否是s2的子串,返回true或false

下一篇:JavaScript - 运算符

赞(0)

共有 条评论 网友评论

验证码: 看不清楚?
    关注微信小程序
    程序员编程王-随时随地学编程

    扫描二维码或查找【程序员编程王】

    可以随时随地学编程啦!

    技术文章导航 更多>
    扫一扫关注最新编程教程