Leetcode 【485、1004、1052】

问题描述：【Array】485. Max Consecutive Ones

解题思路：

因为要找最长连续 1 子数组的长度，所以我们只需要遍历一次，记录每段连续 1 的长度；如果遇到 0，就更新当前最大长度，然后当前长度清零，继续向后遍历。时间复杂度为 O(n)。

Python3 实现：

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        max_ = tem = 0
        for i in range(len(nums)):
            if nums[i] == 0:
                max_ = max(max_, tem)  # 更新当前最大长度
                tem = 0
            else:
                tem += 1
        return max(max_, tem)

---

问题描述：【Array】487. Max Consecutive Ones

收费暂时做不了 hhh~ 题目是最多改变其中 1 个 0 变成 1，然后求最长连续 1 子数组的长度。可以采用滑动窗口的做法，在下面的 1004 题有具体的解法，代码和 1004 完全一样。

---

问题描述：【Sliding Window】1004. Max Consecutive Ones III

解题思路：

这道题是最多改变 K 个 1 变成 0，然后求最长连续 1 子数组的长度。很容易想到滑动窗口的思路（487 做法和本题做法一致，只不过 487 中 K = 1）：

我们来定义本题的滑动窗口：因为肯定将所有 K 个 0 改成 1 才能获得最大长度，因此滑动窗口中记录包含 K 个 0 之后的最长连续 1 子数组。注意到这个滑动窗口的大小是不固定的，因此，我们在滑动的过程中，要记录滑动窗口的起始位置（终止位置不用记，因为终止位置就是当前遍历的位置）。

如何更新滑动窗口呢？如果我们的滑动窗口中已经有 K 个 0 了，后面又遇到一个 0，那么我们就要移动滑动窗口，根据滑动窗口的起始位置找到窗口中最前面的 0，然后这个 0 的下一个位置就是新滑动窗口的起始位置。注意，在这个过程中，还要减小滑动窗口的长度。

这样，我们只需要遍历 1 次，不断更新最大长度，就能得到结果。

注意：刚开始时滑动窗口中 0 的个数如果小于 K，我们只拓展窗口，不更新窗口的起始位置（最开始的起始位置为 0）。

Python3 实现：

class Solution:
    def longestOnes(self, A: List[int], K: int) -> int:
        sliding_window = 0  # 滑动窗口
        begin = 0  # 滑动窗口的起始位置
        nums0 = 0  # 滑动窗口中0的个数
        max_ = 0
        for i in range(len(A)):
            sliding_window += 1  # 拓展窗口长度
            if nums0 < K:  # 滑动窗口中 0 的个数小于 K，只拓展窗口
                if A[i] == 0:
                    nums0 += 1
            elif nums0 == K:
                if A[i] == 0:  # 如果再有 0 出现，更新滑动窗口
                    while A[begin] == 1:  # 找到滑动窗口中第1个0的位置
                        begin += 1
                        sliding_window -= 1
                    begin += 1  # 新滑动窗口的起始位置
                    sliding_window -= 1
            max_ = max(max_, sliding_window)  # 更新最大长度
        return max_

---

问题描述：【Sliding Window、DP、Array】1052. Grumpy Bookstore Owner

解题思路：

方法1（暴力 O(N^2)，TLE）：

• 根据 customers 和 grumpy 数组，可以统计出不使用 X 技巧能得到的一个初始的满意度总和；
• 再考虑使用 X 技巧，对于每个位置，将长度为 X 的窗口中 grupmy[i] == 1 的 custpmers[i] 也加入到初始满意度中，然后更新最大满意度。

这样，时间复杂度为 O(N*X)，由于 X 也可能达到 N 的长度级别，因此为 O(N^2)，超时。

方法2（DP O(N^2)，勉强 AC）：

尝试了一下动态规划，虽然时间复杂度还是 O(N^2)，但勉强 AC 了。DP 思路如下：

• 用 dp1[N] 记录不使用 X 技巧的累加初始满意度，dp2[N] 记录使用 X 技巧的最大满意度，最后 dp2[-1] 就是答案；
• dp1[N] 的状态转移方程很容易 dp1[i] = (dp1[i-1] + customers[i-1]) if grumpy[i-1] == 0 else dp1[i-1]；
• dp2[N] 的状态转移方程为：dp2[i] = (dp2[i-1] + customers[i-1]) if grumpy[i-1] == 0 else max(dp2[i-1], dp1[i-X] + sum(customers[i-X:i]))，含义是如果 grumpy[i-1] 为 0，则老板不会生气，dp[i] 直接在 dp2[i-1] 的基础上加上 customers[i-1] 就好；如果 grumpy[i-1] 为 1，则老板生气，dp2[i] 的值取决于 dp2[i-1] （前面已经生过气）和 dp1[i-X] + sum(customers[i-X:i]) （当前生气，最大满意度为前 dp1[i-X] 和这段 X 长度大小的窗口中的数字之和）的最大值。
• 初始时 dp[i] 中 i < X，无论生气与否，dp2[i] = dp2[i-1] + customers[i-1]，因为 X 技巧可以充分展现。

但是，实际上这种做法还是 O(N*X) 的时间复杂度，但是竟然勉强 AC 了（可能脸好吧）。

Python3 实现（DP）：

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
        N = len(customers)
        dp1 = [0] * (N + 1)  # 不使用 X 技巧的累加初始满意度
        dp2 = [0] * (N + 1)  # 使用 X 技巧的最大满意度
        for i in range(1, N + 1):
            if grumpy[i-1] == 0:
                dp1[i] = dp1[i-1] + customers[i-1]
            else:
                dp1[i] = dp1[i-1]
        for i in range(1, N + 1):
            if grumpy[i-1] == 0 or i-X-1 < 0:
                dp2[i] = dp2[i-1] + customers[i-1]
            else:
                dp2[i] = max(dp2[i-1], dp1[i-X] + sum(customers[i-X:i]))
        return dp2[-1]

方法3（Sliding Window O(N)，AC）：

这也是一道经典的利用滑动窗口解决问题的题目。

我们来定义本题的滑动窗口：因为肯定当技能 X 发挥时能获得的满意度最大，且这个窗口是连续的，因此窗口的大小是固定的。长度为 X 的滑动窗口中记录增加的满意度。

• 先求出不使用 X 技巧的初始满意度；
• 因为窗口中记录使用 X 技巧增加的满意度，所以它等于窗口中 grumpy[i] 为 1 的所有 customers[i] 之和；
• 窗口每次都向右移动一位，刚开始窗口大小小于 X，那么只要是 grumpy[i] == 1 就增加满意度（因为可以充分发挥 X 技巧）；当窗口大小等于 X 时，滑动过程中始终保持 X 长度；
• 当窗口大小等于 X，如果出现一个 grumpy[j] == 1，则窗口增加满意度 customers[j]；同时，如果移出去的 grumpy[j-X] == 1，那么滑动窗口的满意度要减去满意度 customers[j-X]；
• 每次移动窗口，都更新使用 X 技巧增加的满意度的最大值；
• 最后，初始满意度加上使用 X 技巧增加的满意度的最大值就是总的最大满意度。

这样，时间复杂度为 O(N)。

Python3 实现（Sliding Window）：

class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
        N = len(customers)
        initial_satisfied = sum([customers[i] for i in range(N) if grumpy[i] == 0])  # 初始的满意度
        sliding_window = 0  # 大小为X的滑动窗口中保存增加的满意度
        add_satisfied = 0  # 大小为X的滑动窗口中增加的满意度的最大值
        for i in range(N):
            if i < X and grumpy[i] == 1:  # 没有达到窗口大小
                sliding_window += customers[i]
            elif i >= X:
                if grumpy[i] == 1:
                    sliding_window += customers[i]  # 滑动窗口中增加当前满意度
                if grumpy[i-X] == 1:
                    sliding_window -= customers[i-X]  # 滑动窗口移除满意度
            add_satisfied = max(add_satisfied, sliding_window)
        return initial_satisfied + add_satisfied  # 两者之和为最终满意度