[栈]leetcode2197：替换数组中的非互质数(hard)

题目：

题解：

思路：用栈模拟相邻元素的删除操作

代码如下：

using LL = long long;
class Solution {
public:
    // 相邻元素的删除，用栈思考才是最简单的方式
    vector replaceNonCoprimes(vector& q) {
        // 初始化栈
        vector res;res.push_back(q[0]);
        int n=q.size();
        for(int i=1;i
           res.push_back(q[i]);
           // 每次从栈中取栈顶的两个元素，判断是否为非互质数：是就进行替换；不是就退出栈
           while(res.size()>1)
           {
               int x=res.back(),y=res.at(res.size()-2);
               // 求x y 的最大公约数
               int g=gcd(x,y);
               // 最大公约数为1，表示为互质数，进行退栈
               if(g==1)break;
               // 最大公约数不为1，表示为非互质数，则进行替换
               res.pop_back();
               res.back()=x/g*y;
           }
        }
        return res;
    }
};