題目： LeetCode - 1046. Last Stone Weight

題目說明

給一個陣列，每次找出最大及次大的值，若是兩者相同則消除，否則消除小的，而大的值改為兩者相減。

解題思路

  • 解法一：每次都從陣列中取出最大及次大的值，並同時將陣列該位置的值改為 0。使用 pair 儲存，first 放值，second 放 index。

  • 解法二：使用 priority queue。

參考解法

解法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    pair<int, int> findMax(vector<int>& stones)
    {
        pair<int, int> max;
        max = {stones[0], 0};
        for(int i = 1; i < stones.size(); ++i)
            if(stones[i] > max.first)
                max = {stones[i], i};
        stones[max.second] = 0;
        return max;
    }
    
    int lastStoneWeight(vector<int>& stones) {
        pair<int, int> x, y;
        do
        {
            y = findMax(stones);
            x = findMax(stones);
            if(y != x)
                stones[y.second] = y.first - x.first;
        }while(x.first != 0);
        return y.first;
    }
};

解法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:   
    int lastStoneWeight(vector<int>& stones) {
        int y, x;
        priority_queue<int> maxheap;
        for(auto& i : stones)
            maxheap.push(i);
        while(maxheap.size() > 1)
        {
            y = maxheap.top();
            maxheap.pop();
            x = maxheap.top();
            maxheap.pop();
            if(y != x)
                maxheap.push(y - x);
        }
        return maxheap.empty() ? 0 : maxheap.top();
    }
};