Java-queue-heap

[conchincradle]

使用PriorityQueue

Queue q = new PriorityQueue<>();

offer poll size peek

[conchincradle]

max root heap

Queue<Integer> queue = new PriorityQueue<>((a,b)->{
            return b-a;
        });

[conchincradle]

1046. Last Stone Weight Return the weight of the last remaining stone. If there are no stones left, return 0. Constraints:

1 <= stones.length <= 30 1 <= stones[i] <= 1000

[conchincradle]

    public int lastStoneWeight(int[] stones) {
        Arrays.sort(stones);
        Queue<Integer> queue = new PriorityQueue<>((a,b)->{
            return b-a;
        });
        for(int stone: stones){
            queue.offer(stone);
        } 
        while(queue.size()>=2){
            int stone1 = queue.poll();
            int stone2 = queue.poll();
            int left  = stone1-stone2;
            if(left!=0){
                queue.offer(left);
            }
// improve
// if(stone1>stone2) queue.offer(stone1-stone2);
        }
        if(queue.isEmpty()) return 0;
        return queue.poll();
// return queue.isEmpty()?0:queue.poll();

    }

[conchincradle]

有时候面试官考得就是算法思维和思路，先写一个正常思维得，然后再优化，就会表现出自己得思考而不是背答案 三元表达式要牢记 然后我觉得>=2 相比于>1， 要更加直观，表现出最少得2个，而不是说大于一个

[conchincradle]

时空复杂度分析 堆排序怎么实现的 怎么插入新元素 时间复杂度 堆排序中建堆过程时间复杂度O(n)怎么来的？ 首先就是堆 sapce complexity, linea O(n) for heap then time, construct a max root heap is linear O(n) then the best, we poll n-1, every time we poll , delete is O(log n) the worst is, poll n, insert n/2, poll n/2, insert n/4, that is near 2n, that is O(n) times poll (delete ) and insert

so that is O(nlog(n))