Heap¶
Table of Contents¶
- 1046. Last Stone Weight (Easy)
1046. Last Stone Weight¶
"""
- Heap
- Time: O(n log n); Space: O(n)
- 0/1 Knapsack
- Time: O(n); Space: O(n)
"""
from heapq import heapify, heappop, heappush
from typing import List
# Heap
def lastStoneWeightHeap(stones: List[int]) -> int:
maxHeap = [-s for s in stones]
heapify(maxHeap)
while len(maxHeap) > 1:
s1 = heappop(maxHeap)
s2 = heappop(maxHeap)
if s1 != s2:
heappush(maxHeap, s1 - s2)
return -maxHeap[0] if maxHeap else 0
# 0/1 Knapsack
def lastStoneWeightKnapsack(stones: List[int]) -> int:
total = sum(stones)
target = total // 2
dp = [0 for _ in range(target + 1)]
for i in stones:
for j in range(target, i - 1, -1):
dp[j] = max(dp[j], dp[j - i] + i)
return total - 2 * dp[target]
if __name__ == "__main__":
stones = [2, 7, 4, 1, 8, 1]
assert lastStoneWeightHeap(stones) == 1
assert lastStoneWeightKnapsack(stones) == 1
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int lastStoneWeight(vector<int> &stones) {
priority_queue<int> maxHeap(stones.begin(), stones.end());
// Only while there are at least two stones to smash
while (maxHeap.size() > 1) {
int first = maxHeap.top();
maxHeap.pop();
int second = maxHeap.top();
maxHeap.pop();
if (first != second) {
maxHeap.push(first - second);
}
}
return maxHeap.empty() ? 0 : maxHeap.top();
}
int main() {
vector<int> stones = {2, 7, 4, 1, 8, 1};
cout << lastStoneWeight(stones) << endl; // 1
return 0;
}