剑指offer--构建乘积数组

题目描述
给定一个数组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]。不能使用除法。

思路：
就是计算这个元素之前所有元素积和之后所有元素积。如果没计算一个元素都要将前面和后面所有元素撑起来复杂度是O（n2），这里计算前向乘积数组，每个元素都是当前元素和之前元素乘积，反向数组每个元素是当前位置元素与后面元素乘积。注意：当vector动态变化时不要使用vector.size()是不准的。

class Solution {
public:
	vector<int> multiply(const vector<int>& A) {
		vector<int> forward, ret;
		stack<int> backward;
		for (int i = 0; i < A.size(); i++)
		{
			if (i == 0)
			{
				forward.push_back(A[0]);
				backward.push(A[A.size() - 1]);
			}
			else
			{
				forward.push_back(A[i] * forward[i - 1]);
				backward.push(backward.top() * A[A.size() - i - 1]);
			}
		}
		backward