Top 100 Linked Question 修炼------第238题、第239题

238. Product of Array Except Self

题目链接

题目解释：给出一个含有n个整数的数组（n>1），返回这样一个数组：数组中的元素为除可当前角标的元素外的所有元素之积。

Example:

Input:  
[1,2,3,4]

Output: 
[24,12,8,6]

注意：解决这个问题的时候不能采用除法，并且时间复杂度需要为O（n）.

更进一步：你能否使用常数个空间来解决呢（输出的输入不被计算为额外的空间）。

题目分析：首先能够想到最简单的方法就是求出所有元素的乘积，然后将所得的乘积除以原本元素中的当前元素，这样就很容易得到最后的output数组了。但是，很显然，题目一开始就禁止了我们采用除法这个手段。只能是另辟蹊径了。

我们还是可以申请大小为 n 的空间 result 用于返回结果，由于题目要求不能出现除运算，所以本题的基本思路是：

1. 申请两个大小为 n 的数组

2. 第一个数组的第 i 个元素存储第0个到第 i-1 个元素的乘积

3. 第二个数组的第 i 个元素存储第 i+1 到最后一个元素的乘积

4. 然后将两个数组的元素"交叉相乘"即可得到最后的结果

    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # 先给两个数组进行初始化值
        dp1 = [1]
        dp2 = [1]
        for i in range(len(nums) - 1):
            dp1.append(dp1[i] * nums[i])
            dp2.append(dp2[i] * nums[-i - 1])

        output = []
        # 对两个数组进行交叉相乘
        for i in range(len(dp1)):
            output.append(dp1[i] * dp2[-i - 1])
        return output

239. Sliding Window Maximum

题目链接

题目解释：给定一个数组nums，有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。 您只能在窗口中看到k个数。 每次滑动窗口向右移动一个位置。 返回最大滑动窗口。

Example:

Input: nums = 
[1,3,-1,-3,5,3,6,7]
, and k = 3
Output: 
[3,3,5,5,6,7] 
Explanation: 

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Note: 

假设k是有效的，即1≤k≤输入数组的长度。

更进一步:
你能在线性时间内得到最终的结果么？

题目分析：既然题目已经说明了使用滑窗法来解决问题，那么我们直接就是采用移动窗口来解决问题。

    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if k>len(nums):
            return []
        if not nums:
            return []
        res=[]
        i=0
        while (i+k)<len(nums)+1:
            res.append(max(nums[i:i+k]))
            i+=1
        return res

总结

2019/5/23：准备考试的一周，心慌慌