two pass

238. Product of Array Except Self

Difficulty: Medium

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:

Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Hide Company Tags Amazon LinkedIn Apple Facebook Microsoft

思路：求除了n[i]以外的所有数的乘积，那么可以分为两部分考虑，[0~n-2]的乘积和[1~n-1]的乘积，用结果array分别在乘起来。所以，left遍历一个pass，right遍历一个pass。

eg: input [1, 2, 3, 4]

output_left[ 1, 12, 12*3]

output_right[234, 134, 124 ]

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        left, right = 1, 1
        res = [1]*len(nums)
        for i in range(len(nums) -1):
            left *= nums[i]
            res[i +1] *= left
        for j in range(len(nums) - 1, 0, -1):
            right *= nums[j]
            res[j-1]*= right
        return res

42. Trapping Rain Water

Difficulty: Hard

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Hide Company Tags Google Twitter Zenefits Amazon Apple Bloomberg

思路：对任意一个点，只有当他两边中最小那个点都比他大才能积水。

方法一： two pass：用数组left存放对每个点来说左边最大的高度；用数组right存放对每个点来说右边最大的高度。最后每个点的水是min（l，r）-cur。注意，两边至少有一个比cur大才能有水，最左边和最右边为0没水。

eg: height: 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1

max-left: 0 0 1 1 2 2 2 2 3 3 3 3 (left -> right)

max-right: 3 3 3 3 3 3 3 2 2 2 1 0 (right <- left)

方法二： one pass： 用premax存左边最大的点，一个stack 存小于premax的点，当发现新的比premax还大的点时，stack中的点逐个弹出，premax减去这些点就是水的体积。最后替换最大点。注意的是如果遍历完array，stack中还有数，说明右边还有可能有水，在从右到左的弹出stack中的数计算最后的水。

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        '''two pass: find max left for each bar, then max right for each bar''' 
        # l, r = [0], [0]*len(height)
        # res = 0
        # for i in range(1, len(height)):
        #     l.append(max(height[i-1], l[i-1]))

        # for j in range(len(height) - 2, -1,-1):
        #     r[j] = max(r[j+1], height[j+1])
        #     if min(l[j], r[j]) - height[j] > 0:
        #         res += min(l[j], r[j]) - height[j]

        # return res

        '''use only one stack to do the almost same thing'''
        stack = []
        res, premax = 0, 0
        for i in height:
            if i >= premax:
                while stack:
                    cur = stack.pop()
                    res += premax - cur
                premax = i
            else:
                stack.append(i)
        if stack:
            maxr = stack.pop()
        while stack:
            newr = stack.pop()
            if newr >= maxr:
                maxr = newr
            else:
                res += maxr - newr
        return res