Last Updated on 2022-04-07 by Clay
題目
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 weightxis destroyed, and the stone of weightyhas new weighty - x.
At the end of the game, there is at most one stone left.
Return the smallest possible weight of the left 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 <= 301 <= stones[i] <= 1000
題目輸入一數值陣列，陣列中的每一個數值代表一顆石頭的重量。我們要把最重的石頭與次重的石頭相撞，最重的石頭會剩下種量相減之後的結果，次重的石頭會消失。（如果兩石頭重量相同則兩者都消失）
我們要回傳的，就是最後當石頭只剩下一顆時的重量；如果一顆都不剩，則回傳 0。
解題思路
排序解法
最暴力的解法就是直接將陣列排序，並將最後兩者的數值相減並刪除大者（兩者相同時則一齊刪除）。
排序解法複雜度
相減的過程得做 n-1 次，每次排序的時間複雜度是 nlog(n)，所以最終的時間複雜度應是誇張的 n^2 * log(n)。
| Time complexity | O(n^2 * log(n)) |
| Space complexity | O(1) |
排序解法 C++ 範例程式碼
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
// Sort
sort(stones.begin(), stones.end());
while (stones.size() > 1) {
stones[stones.size()-2] = stones.back() - stones[stones.size()-2];
stones.pop_back();
if (stones.back() == 0) stones.pop_back();
// Sort
for (int i=stones.size()-1; i>0; --i) {
if (stones[i] < stones[i-1]) {
swap(stones[i], stones[i-1]);
}
else break;
}
}
return stones.empty() ? 0 : stones.front();
}
};排序解法 Python 範例程式碼
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
while len(stones) > 1:
# Sort
stones.sort()
# Destroy
stones[-2] = stones[-1] - stones[-2]
stones.pop()
if stones[-1] == 0: stones.pop()
return stones[0] if len(stones) == 1 else 0優先權佇列解法
另一個很直覺的解法，就是使用優先權佇列（priority queue）。我們每次返回的數值都是當前最重的石頭重量，連續取出兩次並相減後再將新值推回佇列中。
優先權佇列複雜度
| Time complexity | O(n) |
| Space complexity | O(n) |
Heap 解法 C++ 範例程式碼
class Solution {
public:
int lastStoneWeight(vector<int>& stones) {
// Init
priority_queue<int> pq(stones.begin(), stones.end());
int w1 = 0;
int w2 = 0;
// Destroy
while (pq.size() > 1) {
// w1
w1 = pq.top();
pq.pop();
// w2
w2 = pq.top();
pq.pop();
// New value
if (w1 - w2 != 0) {
pq.push(w1-w2);
}
}
return pq.empty() ? 0 : pq.top();
}
};
由於 Python 沒有優先權佇列（倒是有 heap），所以暫時沒有用這個方法來解題。