数组和窗口-贪心算法
互联网 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)
- 2019-07-07Java编写中容易搞错的一些东西
- 2021-04-12Spring @Required 注释
- 2021-04-12Spring @Autowired 注释
- 2021-04-12Spring @Qualifier 注释
- 2021-04-12Spring JSR-250 注释
- 2021-04-12Spring 基于 Java 的配置
- 2021-04-12Spring 中的事件处理
- 2021-04-12Spring 中的自定义事件
- 2021-04-12Spring 中基于 AOP 的 XML架构
- 2021-04-12Spring 中基于 AOP 的 @AspectJ
关注微信小程序
扫描二维码或查找【程序员编程王】
可以随时随地学编程啦！
技术文章导航
更多>
共有 条评论 网友评论