LeetCode（Heap)1046. Last Stone Weight

我会带着你远行 2023-09-24 23:45 47阅读 0赞

# 1.问题 #

You are given an array of integers stones where stones\[i\] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

If x == y, both stones are destroyed, and  
If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.  
At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

Example 1:

> Input: stones = \[2,7,4,1,8,1\]  
> Output: 1  
> Explanation:  
> We combine 7 and 8 to get 1 so the array converts to \[2,4,1,1,1\] then,  
> we combine 2 and 4 to get 2 so the array converts to \[2,1,1,1\] then,  
> we combine 2 and 1 to get 1 so the array converts to \[1,1,1\] then,  
> we combine 1 and 1 to get 0 so the array converts to \[1\] then that’s the value of the last stone.

Example 2:

> Input: stones = \[1\]  
> Output: 1

Constraints:

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

## 方法1： ##

> List 来存储石头的重量，通过排序和每次取出最大的两个元素来模拟将石头进行粉碎的过程，直到最终只剩下 0 个或者 1 个石头为止。时间复杂度为 O(nlogn)，空间复杂度为 O(n)。

## 方法2： ##

> 1.创建一个最大堆  
> 2.将所有石头的重量放入最大堆中  
> 3.只要最大堆中还有两个或以上的元素  
> 4.弹出最大的石头  
> 5.再次弹出次大的石头  
> 6.只有当两块石头重量不一样时才进行操作  
> 7.将两块石头的差值再放入最大堆中  
> 8.返回最后剩下的石头重量，如果最大堆为空，则说明没有剩下的石头，返回0

## 方法3： ##

> 实现了对一个整数数组中的石头进行碰撞操作，直到最后只剩下一个石头，然后返回该石头的重量。其中，每次碰撞操作中，较重的石头会砸碎较轻的石头，得到新的石头，直到最后只剩下一个石头。

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public int lastStoneWeight(int[] stones) {
        
            Arrays.sort(stones); //将数组排序
            List<Integer> list = new ArrayList<>();
            for (int i = stones.length - 1; i >= 0; i--) {
         //将排序后的数组元素添加到List中
                list.add(stones[i]);
            }
            while (list.size() >= 2) {
         //只要List中元素数量大于等于2个
                int stone1 = list.get(0); //取出List中最大的元素
                int stone2 = list.get(1); //取出List中次大的元素
                if (stone1 > stone2) {
         //如果最大元素大于次大元素
                    list.set(0, stone1 - stone2); //将最大元素的值更新为两者差值
                    list.remove(1); //移除次大元素
                } else {
         //如果最大元素等于次大元素
                    list.remove(0); //移除最大元素
                    list.remove(0); //移除次大元素
                }
                Collections.sort(list, Collections.reverseOrder()); //每次更新完元素后，重新排序List
            }
            if (list.size() == 0) {
         //如果List为空
                return 0; //返回0
            } else {
        
                return list.get(0); //否则返回List中剩下的元素
            }
        }
    }

## 代码2： ##

class Solution {
        
    	public int lastStoneWeight(int[] stones) {
        
    		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
    		for(int st: stones)
    			pq.offer(st);
    	
    		while(pq.size() > 1) {
        
    			int f = pq.poll();
    			int s = pq.poll();
    			if(f != s) 
    				pq.offer(f-s);
    		}
    	
    		return pq.isEmpty() ? 0 : pq.peek();
    	}
    }

> 解题思路基本相同

class Solution {
        
        public static int lastStoneWeight(int[] stones) {
        
            PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
            for(int st: stones)
                pq.offer(st);
    
            while(pq.size() > 1) {
        
                 pq.offer(pq.poll()-pq.poll());
            }
            return pq.isEmpty() ? 0 : pq.peek();
        }
    }

class Solution {
        
        public int lastStoneWeight(int[] stones) {
        
            PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a); //创建一个最大堆
            for (int stone : stones) {
        
                maxHeap.offer(stone); //将所有石头的重量放入最大堆中
            }
            while (maxHeap.size() > 1) {
         //只要最大堆中还有两个或以上的元素
                int stone1 = maxHeap.poll(); //弹出最大的石头
                int stone2 = maxHeap.poll(); //再次弹出次大的石头
                if (stone1 != stone2) {
         //只有当两块石头重量不一样时才进行操作
                    maxHeap.offer(stone1 - stone2); //将两块石头的差值再放入最大堆中
                }
            }
            return maxHeap.isEmpty() ? 0 : maxHeap.peek(); //返回最后剩下的石头重量，如果最大堆为空，则说明没有剩下的石头，返回0
        }
    }

## 代码3： ##

class Solution {
        
    	public int lastStoneWeight(int[] stones) {
        
    	    // 如果数组长度为 1，直接返回该元素
    	    if (stones.length == 1) {
        
    	        return stones[0];
    	    }
    	    
    	    // 对数组进行排序，从小到大
    	    Arrays.sort(stones);
    	    int y = stones.length - 1;
    	    int x = stones.length - 2;
    	    
    	    // 当 x>=0 时，继续执行循环
    	    while (x >= 0) {
        
    	        // 如果当前两个石头的重量相同，则两个石头都消失
    	        if (stones[x] == stones[y]) {
        
    	            stones[x] = 0;
    	            stones[y] = 0;
    	        } else {
        
    	            // 否则，较重的石头砸碎较轻的石头，得到新的石头
    	            stones[y] -= stones[x];
    	            stones[x] = 0;
    	        }
    	        
    	        // 对数组进行排序，从小到大
    	        Arrays.sort(stones);
    	        // 如果 x 位置对应的石头被消失了，跳出循环
    	        if (stones[x] == 0) {
        
    	            break;
    	        }
    	    }
    	    
    	    // 返回最后一个石头的重量
    	    return stones[y];
    	}
    }