2197. 替換數組中的非互質數

小貼士：C++當中能透過__gcd(a,b)得到最大公因數，lcm(a,b)得到最小公倍數

思路

因為題目要求選出兩個相鄰的數字刪除，並且一個數字可以用了再用，可能會刪除掉許多自己一旁的數字。
因此使用 stack，遍歷陣列，拿現在的數字不斷披荊斬棘（不斷刪除數字，把自己變成最小公倍數），
直到拚盡全力無法戰勝（互質），放進stack，之後的數字能來挑戰它。
可以直接用 vector 模擬 stack，迴圈結束後答案就出來了，比較快（因為不需要轉成 vector）。

程式碼

1.使用陣列模擬棧（stack）

class Solution {
public:
    vector<int> replaceNonCoprimes(vector<int>& nums) {
        int n = nums.size();
        vector<int> res;
        for(int num : nums) {
            while(!res.empty() && __gcd(res.back(), num) != 1) { // 不互質，可更新
                num = lcm(num, res.back()); // 替換為最小公倍數
                res.pop_back(); // 丟掉數字
            }
            res.push_back(num);
        }
        return res;
    }
};

2.不使用額外空間

class Solution {
public:
    vector<int> replaceNonCoprimes(vector<int>& nums) {
        int n = nums.size();
        int j = -1; // 用當前的 nums 作為第一種方法的 stack, j 代表當前棧頂的位置
        for(int i = 0; i < nums.size(); ++i) {
            while(j >= 0 && __gcd(nums[j], nums[i]) != 1) {
                nums[i] = lcm(nums[i], nums[j]);
                --j;
            }
            ++j;
            nums[j] = nums[i];
        }
        // j 是 index, 不是大小。
        nums.resize(j + 1);
        return nums;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{C})$ ，$n$ 是 $nums$ 的大小，其中 $O(\log{C})$ 是計算最大公因數的複雜度
• 空間複雜度：$O(n)$ 或是 $O(1)$