Grind75第2天 | 238.除自身以外数组的乘积、75.颜色分类、11.盛最多水的容器

238.除自身以外数组的乘积

题目链接：https://leetcode.com/problems/product-of-array-except-self

解法：

这个题有follow up， 要求优化到空间复杂度为O(1)，所以给出baseline和follow up的解法。

Baseline：利用索引左侧所有数字的乘积和右侧所有数字的乘积（即前缀与后缀）相乘得到答案。因此需要两个列表：L 和 R，对于nums中的索引i，L[i] 表示索引i左侧所有数字的乘积，R[i] 表示索引i右侧所以数字的乘积，那么L[i] *?R[i] 就是除自身以外数组的乘积。

空间复杂度为O(n)

Follow up：根据表格的主对角线（全为?1?），可将表格分为?上三角?和?下三角?两部分。分别迭代计算下三角和上三角两部分的乘积。

空间复杂度为O(1)

参考题解：上三角和下三角

边界条件：无

时间复杂度：O(n)

空间复杂度：

# 空间复杂度 O(n)
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        L, R = [1] * length, [1] * length
        res = [1] * length

        for i in range(1, length):
            L[i] = L[i-1] * nums[i-1]
        
        for i in range(length-2, -1, -1):
            R[i] = R[i+1] * nums[i+1]

        for i in range(length):
            res[i] = L[i] * R[i]

        return res

# 空间复杂度 O(1)
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        res = [1] * length
        temp = 1

        for i in range(1, length):
            res[i] = res[i-1] * nums[i-1]
        
        for i in range(length-2, -1, -1):
            temp *= nums[i+1]
            res[i] *= temp

        return res

75.颜色分类

题目链接：https://leetcode.com/problems/sort-colors

解法：

注意这个题要求原地修改，还有follow up要求只能扫描一次。

Baseline：baseline的解法是统计0,1,2三个元素的个数，然后在原数组中修改。需要扫描两次。

Follow up：使用三个指针：i，j，k。[0, i) 区间都是0，[i, j) 都是1，[k+1, length-1]都是2，如下图所示。

初始化时，让0和2的区间都为空，那么i初始化为0，k初始化为length-1。

如果nums[j] = 0，由于 nums[i]是位于1的区间的，那么需要交换，交换后[0, i+1)是0区间了，[i+1, j+1) 是1区间了，所以i和j都得加1。

如果nums[j] = 2，由于那么和 nums[k] 进行交换，交换后，[k, length)是新的2区间了，所以k需要减1。而交换之前的nums[k]不知道是什么数值，不一定是1，所以j不用加1。

如果nums[j] = 1，那么j直接加1就行。

如此，直到 j 大于 k，终止。

参考题解：75. 颜色分类 | 手写图解版思路 + 代码讲解_哔哩哔哩_bilibili

边界条件：无

时间复杂度：O(n)

空间复杂度：O(1)

# baseline
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        count = [0] * 3
        for i in nums:
            count[i] += 1
        
        for i in range(len(nums)):
            if i < count[0]:
                nums[i] = 0
            elif i < count[0] + count[1]:
                nums[i] = 1
            else:
                nums[i] = 2

# 扫描一次
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        length = len(nums)
        if length < 2:
            return

        zero = 0
        two = length - 1
        i = 0
        # 遵循左闭右开的写法
        while i <= two:
            if nums[i] == 0:
                nums[i], nums[zero] = nums[zero], nums[i]
                zero += 1
                i += 1
            elif nums[i] == 1:
                i += 1
            else:
                nums[i], nums[two] = nums[two], nums[i]
                two -= 1

11.盛最多水的容器

题目链接：https://leetcode.com/problems/container-with-most-water

解法：

这个题用双指针。基本的思路是，双指针为i和j，容器的盛水量由短板决定 min(h[i], h[j]) * (j - i)。双指针从两端往中间移动，移动的过程中，（j - i）一定是变小的，那么为了得到更大的容积，就需要短板变大，所以只能移动短板。到两个指针相遇时，停止。

参考题解：双指针

边界条件：无

时间复杂度：O(n)

空间复杂度：O(1)

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i, j, res = 0, len(height) - 1, 0
        while i < j:
            if height[i] < height[j]:
                res = max(res, height[i] * (j - i))
                i += 1
            else:
                res = max(res, height[j] * (j - i))
                j -= 1
        return res