题解 | 两端问优先队列

import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		PriorityQueue<Integer> queue1=new PriorityQueue<>();
		PriorityQueue<Integer> queue2=new PriorityQueue<>((s1,s2)->s2-s1);
		TreeMap<Integer, Integer> map=new TreeMap<>();
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		for (int i = 0; i < n; i++) {
			int op=scanner.nextInt();
			if(op==1) {
				int x=scanner.nextInt();
				map.put(x, map.getOrDefault(x, 0)+1);
				
			}else if(op==2) {
				System.out.println(map.firstKey());
				
			}else if(op==3) {
				System.out.println(map.lastKey());
			}else if(op==4){
				int x=map.firstKey();
				if(map.get(x)>1) {
					map.put(x,map.get(x)-1) ;
				}else {
					map.remove(x);
				}
				
			}else if(op==5) {
				int x=map.lastKey();
				if(map.get(x)>1) {
					map.put(x,map.get(x)-1) ;
				}else {
					map.remove(x);
				}
			}
				
		}

	}

}

这道题我一开始想着用两个优先级相反的队列做，然后用一个数组来存每一个数的数量，结果发现只能过8个测试点，我也不知道问题出在哪，后面学题解的方法，用TreeMap来做，别说确实好用，firstKey可以得到最小键，lastKey可以得到最大键，移除键也可以通过put更新该键存在的数量，如果数量只有1，那么就直接remove