数组和窗口-贪心算法

本文主要是介绍数组和窗口-贪心算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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 }

 

这篇关于数组和窗口-贪心算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！