leetcode (堆->hard) 23,218,239,295,407,786

23 合并K个升序链表

 　　首先最简单的当然是建个堆往里面加，优点是基本不需要思考。。。

public static ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((k1,k2)->k2.val-k1.val);
        for (int i = 0; i < lists.length; i++) {
            ListNode node  = lists[i];
            while (node != null){
                pq.add(node);
                node = node.next;
            }
        }
        if (pq.isEmpty())return null;
        ListNode poll = new ListNode(pq.poll().val);
        while (!pq.isEmpty()){
            ListNode poll1 = pq.poll();
            poll1.next = poll;
            poll = poll1;
        }
        return poll;
    }

　　然后应该这种合并序列的方式应该也是可以使用N指针的方式 堆只需要维护lists.size()大小

public static ListNode mergeKLists(ListNode[] lists) {

        if (lists == null || lists.length == 0){
            return null;
        }
        PriorityQueue<ListNode> pq = new PriorityQueue<>((k1,k2)->k1.val-k2.val);
        for (ListNode listNode : lists) {
            if (listNode == null)continue;
            pq.add(listNode);
        }
        if (pq.isEmpty()){
            return null;
        }
        ListNode poll = pq.poll();
        if (poll.next != null){
            pq.add(poll.next);
        }
        ListNode tp = poll;
        while (!pq.isEmpty()){
            ListNode current = pq.poll();
            if (current.next != null){
                pq.add(current.next);
            }
            tp.next = current;
            tp = tp.next;
        }
        return poll;
    }

218 这题自己真的是毫无头绪，看到的大佬的扫描法感觉是相当的厉害，也是看了好久才明白 点击  传送门 

 　　使用扫描法来解

  public static List<List<Integer>> getSkyline(int[][] buildings) {
        List<List<Integer>> result = new ArrayList<>();
        PriorityQueue<int[]> pq = new PriorityQueue<>((k1,k2)-> k1[0] == k2[0] ? k1[1]-k2[1]:k1[0]-k2[0]);
        for (int[] building : buildings) {
            pq.add(new int[]{building[0],-building[2]});
            pq.add(new int[]{building[1],building[2]});
        }

        int maxHeight = 0;
        TreeMap<Integer,Integer> treeMap = new TreeMap<>((k1,k2)->k2-k1);
        treeMap.put(0,1);
        while (!pq.isEmpty()){
            int[] value = pq.poll();
            int x = value[0];
            int val = value[1];
            if (val < 0){
                //左端点  高度入tree
                treeMap.put(-val,treeMap.getOrDefault(-val,0)+1);
            }else {
                //右端点
                Integer count = treeMap.get(val);
                if (count == 1){
                    treeMap.remove(val);
                }else {
                    treeMap.put(val,--count);
                }
            }
            Integer currentMax = treeMap.keySet().iterator().next();
            if (!currentMax.equals(maxHeight)){
                maxHeight = currentMax;
                result.add(Arrays.asList(x,maxHeight));
            }
        }
        return result;

    }

239 滑动窗口最大值

 　　这个我的思路是用堆来维护，然后每遍历一个值的时候找到堆顶，如果堆顶的元素在滑动窗口内就是正确答案，如果不是就poll继续找。

        if (k == 1)return nums;
        int[] arr = new int[nums.length-k+1];
        PriorityQueue<Integer> pq = new PriorityQueue<>((k1,k2)->nums[k2]-nums[k1]);
        int s = 0;
        for (int i = 0; i < nums.length; i++) {
            pq.add(i);
            if (i >= k-1){
                while (pq.peek() < i+1-k){
                    pq.poll();
                }
                arr[s++] = nums[pq.peek()];
            }
        }
        return arr;

　　当然了 一顿操作猛如虎，一看击败百分五

295 中位数

　　这题按理说是要设计一个数据结构  既要快速找到中位数，又要满足快速的插入新的节点。想法是实现类似一个平衡树，但是太复杂了没实现了。。。 然后通用的思路是双堆法

    PriorityQueue<Integer> big;
    PriorityQueue<Integer> small;
    int size;
    public HeapSimple14() {
        big = new PriorityQueue<>((k1,k2)->k1-k2);
        small = new PriorityQueue<>((k1,k2)->k2-k1);
    }

    public void addNum(int num) {
        size++;
        if ((size &1) != 0){
            big.offer(num);
        }else {
            small.offer(num);
        }
        swap();
    }
    private void swap(){
        if (!big.isEmpty() && !small.isEmpty()){
            while (big.peek() < small.peek()  ){
                Integer bigP = big.poll();
                Integer smallP = small.poll();
                big.offer(smallP);
                small.offer(bigP);
            }
        }
    }
    public double findMedian() {
        if ((size & 1) == 1){
            return big.peek();
        }
        return (double)(big.peek()+small.peek())/2;
    }

407  接雨水2

　　这特么还有三维接雨水的，不知道后面会不会出四维五维。。。

 　　感觉有点难 先放着

786 第k个最小素数分数

　　用堆一阵暴力解决

   public static int[] kthSmallestPrimeFraction(int[] arr, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((k1,k2)-> {
            double a = (double) k1[0]/k1[1];
            double b= (double) k2[0]/k2[1];
            if (a == b){
                return 0;
            }else if (a >b){
                return -1;
            }else {
                return 1;
            }
        });
        for (int i = arr.length-1; i >=0 ; i--) {
            for (int j = 0; j < i; j++) {
                if (pq.size() <k){
                    pq.add(new int[]{arr[j],arr[i]});
                }else {
                    int[] peek = pq.peek();
                    if ((double) arr[j]/arr[i] < (double) peek[0]/peek[1] ){
                        pq.poll();
                        pq.add(new int[]{arr[j],arr[i]});
                    }else {
                        break;
                    }
                }
            }
        }
        
        
        return pq.poll();

    }

　　堆系列继续耻辱结束。。。