题目

给你一个整数数组 nums 。请你对数组执行下述操作：

从 nums 中找出任意两个相邻的 非互质 数。
如果不存在这样的数，终止这一过程。
否则，删除这两个数，并替换为它们的 最小公倍数（Least Common Multiple，LCM）。
只要还能找出两个相邻的非互质数就继续重复这一过程。

返回修改后得到的最终数组。可以证明的是，以任意顺序替换相邻的非互质数都可以得到相同的结果。

生成的测试用例可以保证最终数组中的值 小于或者等于 108 。

两个数字 x 和 y 满足 非互质数 的条件是：GCD(x, y) > 1 ，其中 GCD(x, y) 是 x 和 y 的 最大公约数 。

示例 1 ：

输入：nums = [6,4,3,2,7,6,2] 输出：[12,7,6] 解释：

(6, 4) 是一组非互质数，且 LCM(6, 4) = 12 。得到 nums = [12,3,2,7,6,2] 。
(12, 3) 是一组非互质数，且 LCM(12, 3) = 12 。得到 nums = [12,2,7,6,2] 。
(12, 2) 是一组非互质数，且 LCM(12, 2) = 12 。得到 nums = [12,7,6,2] 。
(6, 2) 是一组非互质数，且 LCM(6, 2) = 6 。得到 nums = [12,7,6] 。现在，nums 中不存在相邻的非互质数。因此，修改后得到的最终数组是 [12,7,6] 。注意，存在其他方法可以获得相同的最终数组。

示例 2 ：

输入：nums = [2,2,1,1,3,3,3] 输出：[2,1,1,3] 解释：

(3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3,3] 。
(3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3] 。
(2, 2) 是一组非互质数，且 LCM(2, 2) = 2 。得到 nums = [2,1,1,3] 。现在，nums 中不存在相邻的非互质数。因此，修改后得到的最终数组是 [2,1,1,3] 。注意，存在其他方法可以获得相同的最终数组。

提示：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
生成的测试用例可以保证最终数组中的值 小于或者等于 10^8 。

解题思路

这是一道非常典型的利用栈（Stack）思想来解决的问题。我们来一步步分析解题思路。

问题的核心是不断合并相邻的非互质数。

当我们合并 nums[i] 和 nums[i+1] 时，它们会被替换成一个新的数 lcm(nums[i], nums[i+1])。
这个新生成的数，现在位于原来 nums[i] 的位置，它的左边邻居是 nums[i-1]。
关键点在于：这个新数 lcm 可能与它左边的邻居 nums[i-1] 也是非互质的，需要继续检查和合并。

这个“处理完当前，回头看前一个”的模式，是使用栈这种数据结构的经典信号。我们可以把最终的结果数组看作一个栈。我们遍历输入数组 nums，每次取出一个数，尝试将它放入我们的结果栈中。

当我们将一个新数 x 放入栈时，我们只需要关心它和栈顶的那个数是否互质。
如果它们非互质，就说明这两个数需要合并。我们把栈顶元素弹出，和 x 计算出新的 LCM，然后用这个新的 LCM 值继续和新的栈顶元素比较。这个过程一直重复，直到 x 和栈顶元素互质，或者栈为空。
如果它们互质，说明无法合并，直接把 x 压入栈顶即可。

这个过程完美地模拟了题目要求的“只要还能找出...就继续重复”的逻辑，并且因为只关心栈顶，所以效率很高。

准备辅助函数：我们需要 gcd(a, b) 和 lcm(a, b) 这两个函数。根据我们之前的讨论，我们可以很方便地写出来。
- gcd(a, b): 使用辗转相除法。
- lcm(a, b): 使用 (a / gcd(a, b)) * b 这个公式来防止整数溢出。因为题目保证最终结果小于等于 10^8，但中间过程的乘积 a * b 可能会很大，所以使用 long long 来进行计算会更安全。
创建结果栈：声明一个 vector 或者 list 作为我们的栈（我们称之为 res）。
遍历输入数组 nums：对于 nums 中的每一个数 x，执行以下操作： a. 将当前数 x 作为一个独立的待处理元素 current_val。 b. 循环检查与合并：只要 res 栈不为空，就执行： i. 取出栈顶元素 top = res.back()。 ii. 计算 g = gcd(top, current_val)。 iii. 如果 g > 1 (非互质)，说明需要合并： - 将栈顶元素弹出 res.pop_back()。 - 用 top 和 current_val 计算出新的 lcm，并更新 current_val 的值：current_val = lcm(top, current_val)。 - 继续这个循环，用更新后的 current_val 和新的栈顶元素继续比较。 iv. 如果 g == 1 (互质)，说明 current_val 和栈顶元素不能合并： - 跳出这个循环。 c. 压入新元素：当内部循环结束后（可能是因为栈空了，或者遇到了互质的邻居），将最终得到的 current_val 压入 res 栈中。
返回结果：遍历完整个 nums 数组后，res 栈中剩下的就是最终的结果数组。

具体代码

class Solution {
public:

    int lcm(const int& a,const int& b) {
        if (a == 0 || b == 0) return 0;
        return (a / gcd(a, b)) * b;
    }

    vector<int> replaceNonCoprimes(vector<int>& nums) {
        vector<int> res;

        for (const int& num : nums) {
            int current_val = num;
            
            while (!res.empty() && gcd(res.back(), current_val) > 1) {
                int top = res.back();
                res.pop_back();
                current_val = lcm(top, current_val); // 更新当前值
            }
            res.push_back(current_val);
        }

        return res;
    }
};

2197. 替换数组中的非互质数

beautifulremi

题目

解题思路

具体代码