[数据结构与算法]leetcode 2197 用栈模拟质数合并

此题并不需要什么算法，模拟即可。但是复杂的模拟方式可能带来很长很丑的代码。

此题说了，任意顺序合并都可以得到相同的结果，所以此题可以用单调栈的思想解决，从左边开始，每次弹出两个，不断合并，如果右边可以合并完成，一定会反馈给左边，还是很玄妙的。

class Solution {
public:
    int gcd(int a, int b)
    {
        if(b == 0)return a;
        return gcd(b, a%b);
    }

    vector<int> replaceNonCoprimes(vector<int>& nums) {
        int n = nums.size();
        vector<int> s;
        for(auto num: nums)
        {
            s.push_back(num);
            while(s.size() > 1)
            {
                int e1 = s.back(); s.pop_back();
                int e2 = s.back(); s.pop_back();
                int _gcd = gcd(e1, e2);
                if(_gcd > 1)s.push_back(e1/_gcd*e2);
                else
                {
                    s.push_back(e2);
                    s.push_back(e1);
                    break;
                }
            }
        }

        return s;

    }
};