剑指 Offer 66. 构建乘积数组

剑指 Offer 66. 构建乘积数组
思路：

如果按照正常的思路就是前后缀分解，计算前面的乘积和，后面的乘积和，最后计算在一起。

b[i]表示a[0] * ... * a[i - 1]。

如果限制了空间，那么就是先维护前面的乘积和数组，然后计算后面乘积的时候在原数组上计算。

代码：

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        int n = a.size();
        vector<int> b(n,1);
        for(int i = 1; i < n; i++) b[i] = a[i - 1] * b[i - 1];

        for(int i = n - 1,s = 1; i >= 0; i--){
            b[i] *= s;
            s *= a[i];
        }
        return b;
    }
};