来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/last-stone-weight/
Analysis
关键点在于每次都能拿到最重的，并且执行过程中可能产生新的较轻的石头。
因此采用优先队列完成（大顶堆）
Solution 【大顶堆】 ( 5ms)
执行用时 : 5 ms, 在Last Stone Weight的Java提交中击败了43.52% 的用户
内存消耗 : 34 MB, 在Last Stone Weight的Java提交中击败了100.00% 的用户
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
public int lastStoneWeight(int[] stones) {
/* 使用优先对列保证每次能拿到最大的数 */
Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return (o2 - o1);
}
});
for (int i = 0; i < stones.length; i++) {
queue.offer(stones[i]);
}
while(queue.size() > 1) {
int x = queue.poll();
int y = queue.poll();
int diff = Math.abs(x - y);
if (diff != 0) {
queue.offer(diff);
}
}
if (queue.isEmpty()) return 0;
return queue.peek();
}
}
|
复杂度分析
时间：$O(NlogN)$
空间：$O(N)$
Analysis
这个思路在于每次都重新排序，
理论上复杂度会更高，但实际更快
是因为每次最多只有一对元素逆序吗。。。
Solution【排序】 ( 1ms)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public int lastStoneWeight(int[] stones) {
int end = stones.length - 1;
int k = 0;
while( k != stones.length && k != stones.length - 1 ){
Arrays.sort(stones);
int x = stones[end - 1];
int y = stones[end];
if( x == y ){
stones[end - 1] = stones[end] = -1;
//end -= 2;
k += 2;
}else{
stones[end - 1] = stones[end] - stones[end - 1];
stones[end] = -1;
k += 1;
}
}
Arrays.sort(stones);
return k == stones.length ? 0 : stones[end];
}
}
|