数组和窗口-贪心算法

互联网 2021/4/8 22:55:09

Description 给定一个整型数组arr和一个大小为w的窗口,窗口从数组最左边滑动到最右边,每次向右滑动一个位置,求出每一次滑动时窗口内最大元素的和。 Input 输入第一行为用例个数, 每个测试用例输入的第一行为数组,每一个元素使用空格隔开;第二行为窗口大小。 Output…
Description 给定一个整型数组arr和一个大小为w的窗口,窗口从数组最左边滑动到最右边,每次向右滑动一个位置,求出每一次滑动时窗口内最大元素的和。 Input 输入第一行为用例个数, 每个测试用例输入的第一行为数组,每一个元素使用空格隔开;第二行为窗口大小。 Output 输出每个测试用例结果。 Sample Input 1  1 4 3 5 4 3 3 6 7 3 Sample Output 1 32   解题思路: 使用双端队列去存储窗口内的元素。贪心策略:每次窗口新增元素,只保留比该元素更大的值,其他的因为没有作用全部删除。 窗口每移动一格,就将新元素x插入队列尾部,如果x前面元素有更小的,则在x出窗口前无法起到作用,可以全部出队。 移出窗口的元素y判断是否是队列首部元素,如果是,则出队,如果不是,说明在队列中之前就被清除了。   代码如下:
 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 w = Integer.parseInt(scan.nextLine());
12             String[] strs = str.split(" ");
13             int n = strs.length;
14             if (w > n) w = n;
15             int[] arr = new int[n];
16             for (int i = 0; i < n; i++)
17                 arr[i] = Integer.parseInt(strs[i]);
18             // 双端队列,这里只存储元素的下标
19             LinkedList<Integer> list = new LinkedList<>();
20             // 初始化
21             list.addLast(0);
22 
23             for (int i = 1; i < w; i++) {
24                 while (list.size() > 0 && arr[list.getLast()] < arr[i])
25                     list.pollLast();
26                 list.addLast(i);
27             }
28             int sum = arr[list.getFirst()];
29             // 窗口移动,增加元素arr[i],除去元素arr[i-w]
30             for (int i = w; i < n; i++) {
31                 // 增加元素arr[i]
32                 while (list.size() > 0 && arr[list.peekLast()] < arr[i])
33                     list.pollLast();
34                 list.addLast(i);
35                 // 除去元素arr[i-w]
36                 if (list.getFirst() == i-w)
37                     list.pollFirst();
38                 sum += arr[list.getFirst()];
39             }
40             System.out.println(sum);
41         }
42         scan.close();
43     }
44 
45 }

 

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

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

上一篇:四合一小说漫画听书视频网站源码 带采集

下一篇:泛型程序设计

赞(0)

共有 条评论 网友评论

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

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

    可以随时随地学编程啦!

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