[算法]最后一块石头的重量——LeetCode1046

题目链接

简单的模拟可解，不过Java竟然自带了priorityqueue，学到了学到了

此外java中无法直接将int数组转linkedList，只能遍历一遍赋值

思路

简单的循环加模拟，由于要对数组进行多次删改，所以考虑使用linkedlist减小开销，然后每次使用自带的sort进行排序

显然耗时爆表

使用最大堆，虽然思路基本一样，但是由于堆的特性，代价会小很多

代码

public int lastStoneWeight(int[] stones) {
        LinkedList ls = new LinkedList();
		for(int e:stones) {
			ls.add(e);
		}
		while(ls.size()!=1&&ls.size()!=0) {
			Collections.sort(ls);
			int max1 = ls.pollLast();
			int max2 = ls.pollLast();
			int te = Math.abs(max2-max1);
			ls.add(te);
		}
		
		if(ls.size()!=0){
			return ls.pop();
		}else {
			return 0;
		}
    }

官方题解：

public int lastStoneWeight(int[] stones) {
        PriorityQueue pq = new PriorityQueue((a, b) -> b - a);
        for (int stone : stones) {
            pq.offer(stone);
        }

        while (pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();
            if (a > b) {
                pq.offer(a - b);
            }
        }
        return pq.isEmpty() ? 0 : pq.poll();
    }

心得

PriorityQueue是基于优先堆的一个无界队列，这个优先队列中的元素可以默认自然排序或者通过提供的Comparator（比较器）在队列实例化的时排序。