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()]);}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！