构建乘积数组

题目描述
给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]A[1]…*A[i-1]A[i+1]…*A[n-1]。不能使用除法。

思路：先求下三角的乘积（即左半部分），再乘以上三角的乘积（即右半部分）。
链接：https://www.nowcoder.com/questionTerminal/94a4d381a68b47b7a8bed86f2975db46
来源：牛客网

B[i]的值可以看作下图的矩阵中每行的乘积。
下三角用连乘可以很容求得，上三角，从下向上也是连乘。
因此我们的思路就很清晰了，先算下三角中的连乘，即我们先算出B[i]中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去。

# -*- coding:utf-8 -*-
class Solution:
	def multiply(self, A):
		if not A:
			return []
		length = len(A) # 不能用[] * length,只能用[None] * length,也不能用B = A,因为这会在B改变后，A也跟着改变，即保持B = A
		B = [None] * length
		# 上三角（前面一部分）
		B[0] = 1
		for i in range(1, length):
			B[i] = B[i - 1] * A[i - 1]
		# 下三角（后面一部分）
		tmp = 1
		for i in range(length - 2, -1, -1):  # 从length - 2开始，不包括-1
			tmp *= A[i + 1]
			B[i] *= tmp
		return B