[leetcode6019]替换数组中的非互质数

https://leetcode-cn.com/problems/replace-non-coprime-numbers-in-array/

咱也不知道着为啥算hard….就是相邻的非互质数 二合一成最小公倍数 之后不断合成 直到数组中没有相邻的互质数

思路 模拟即可 用栈 不断向左边合成 每次判断栈顶两个元素 跑到最后即可

class Solution {
public:
    vector<int> replaceNonCoprimes(vector<int>& nums) {
        vector<int> ans={nums[0]};//入栈
        int n=nums.size();
        for(int i=1;i<n;i++){
            //入栈
            ans.push_back(nums[i]);
            while(ans.size()>1){
                int a=ans.back(),b=ans[ans.size()-2];
                int g=gcd(a,b);
                if(g==1){
                    break;
                }
                ans.pop_back();
                ans.back()*=a/g;
            }
        }
        return ans;
    }
};