题解 | #乳牛各类产奶统计# 前后缀分解

知识点

前后缀分解 前缀和

思路

不能使用除法，我们可以预处理每个位置的前后缀的乘积，然后遍历每个位置用前后缀的乘积来计算得到答案。

时间复杂度

预处理前后缀和

遍历整个数组

整体时间复杂度为

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param milk_amount int整型vector 
     * @return int整型vector
     */
    vector<int> product_except_self(vector<int>& milk_amount) {
        int n = milk_amount.size();
        vector<int> l(n + 1), r(n + 1);
        l[0] = r[0] = 1;
        for (int i = 1; i <= n; i ++) {
            l[i] = l[i - 1] * milk_amount[i - 1];
            r[i] = r[i - 1] * milk_amount[n - i];
        }
        vector<int> res(n);
        for (int i = 0; i < n; i ++) {
            res[i] = l[i] * r[n - i - 1];
        }
        return res;
    }
};