本文主要是介绍P1440 求m区间内的最小值单调队列 Java,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
使用Java会爆内存。
Deque Java自带的双端队列 LinkedList实现,可以从两端进行插入删除操作。
单调队列
时刻维护队列中元素下标位于区间内.
while(dq.peekFirst() <= i - 1 - m)dq.pollFirst();
import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;public class Main {public static void main(String[] args) {Scanner cin = new Scanner(System.in);//shortint n = cin.nextInt();int m = cin.nextInt();int a[] = new int[n + 5];Deque<Integer>dq = new LinkedList<>();for(int i = 0;i < n;i++)a[i] = cin.nextInt();
// dq.push(0);System.out.println(0);for(int i = 1;i < n;i++){while(!dq.isEmpty() && a[dq.peekLast()] > a[i - 1])dq.pollLast();dq.addLast(i - 1);while(dq.peekFirst() <= i - 1 - m)dq.pollFirst();System.out.println(a[dq.peekFirst()]);}}
}
这篇关于P1440 求m区间内的最小值单调队列 Java的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!