class Solution {
public:
    //O(n)时间：分成前后两部分。
    //前半部分：B[i]=B[i-1]*A[i-1]；后半部分：反向遍历，利用tmp累乘A[i],B[i]*=tmp;
    vector<int> multiply(const vector<int>& A) {
        int len = A.size();
        if(len == 0)
            return {};
        vector<int> B(len, A[0]);
        for(int i=1; i<len; i++)//前半部分
            B[i] = B[i-1]*A[i-1];
        
        int tmp = 1;
        for(int i=len-1; i>=0; i--)//后半部分
        {
            B[i] *= tmp;
            tmp *= A[i];
        }
        return B;
    }
};