1046. Last Stone Weight

發表於 | 分類於

problem

solution

option 1 - heap

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        priority_queue<int> pq(stones.begin(), stones.end());
        while(pq.size()!=1){
            int a = pq.top(); pq.pop();
            int b = pq.top(); pq.pop();
            pq.push(a-b);
        }
        return pq.top();
        
    }
};

option 2 - counting sort

1

analysis

  • option 1 - heap
    • time complexity O(nlogn)
    • space complexity O(n)
  • option 2 - sort
    • time complexity O(n)
    • space complexity O(1)