問(wèn)題描述：【Array】485. Max Consecutive Ones
解題思路：
因?yàn)橐易铋L(zhǎng)連續(xù) 1 子數(shù)組的長(zhǎng)度撑教，所以我們只需要遍歷一次，記錄每段連續(xù) 1 的長(zhǎng)度醉拓；如果遇到 0伟姐，就更新當(dāng)前最大長(zhǎng)度，然后當(dāng)前長(zhǎng)度清零亿卤，繼續(xù)向后遍歷愤兵。時(shí)間復(fù)雜度為 O(n)。
Python3 實(shí)現(xiàn)：
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) # 更新當(dāng)前最大長(zhǎng)度
tem = 0
else:
tem += 1
return max(max_, tem)
問(wèn)題描述：【Array】487. Max Consecutive Ones
收費(fèi)暫時(shí)做不了 hhh~ 題目是最多改變其中 1 個(gè) 0 變成 1排吴，然后求最長(zhǎng)連續(xù) 1 子數(shù)組的長(zhǎng)度秆乳。可以采用滑動(dòng)窗口的做法钻哩，在下面的 1004 題有具體的解法屹堰，代碼和 1004 完全一樣。
問(wèn)題描述：【Sliding Window】1004. Max Consecutive Ones III
解題思路：
這道題是最多改變 K 個(gè) 1 變成 0街氢，然后求最長(zhǎng)連續(xù) 1 子數(shù)組的長(zhǎng)度扯键。很容易想到滑動(dòng)窗口的思路（487 做法和本題做法一致，只不過(guò) 487 中 K = 1）：
我們來(lái)定義本題的滑動(dòng)窗口：因?yàn)榭隙▽⑺?K 個(gè) 0 改成 1 才能獲得最大長(zhǎng)度珊肃，因此滑動(dòng)窗口中記錄包含 K 個(gè) 0 之后的最長(zhǎng)連續(xù) 1 子數(shù)組荣刑。注意到這個(gè)滑動(dòng)窗口的大小是不固定的，因此伦乔，我們?cè)诨瑒?dòng)的過(guò)程中厉亏，要記錄滑動(dòng)窗口的起始位置（終止位置不用記，因?yàn)榻K止位置就是當(dāng)前遍歷的位置）烈和。
如何更新滑動(dòng)窗口呢爱只？如果我們的滑動(dòng)窗口中已經(jīng)有 K 個(gè) 0 了，后面又遇到一個(gè) 0招刹，那么我們就要移動(dòng)滑動(dòng)窗口虱颗，根據(jù)滑動(dòng)窗口的起始位置找到窗口中最前面的 0，然后這個(gè) 0 的下一個(gè)位置就是新滑動(dòng)窗口的起始位置蔗喂。注意忘渔，在這個(gè)過(guò)程中，還要減小滑動(dòng)窗口的長(zhǎng)度缰儿。
這樣畦粮，我們只需要遍歷 1 次，不斷更新最大長(zhǎng)度，就能得到結(jié)果宣赔。
注意：剛開(kāi)始時(shí)滑動(dòng)窗口中 0 的個(gè)數(shù)如果小于 K预麸，我們只拓展窗口，不更新窗口的起始位置（最開(kāi)始的起始位置為 0）儒将。
Python3 實(shí)現(xiàn)：
class Solution:
def longestOnes(self, A: List[int], K: int) -> int:
sliding_window = 0 # 滑動(dòng)窗口
begin = 0 # 滑動(dòng)窗口的起始位置
nums0 = 0 # 滑動(dòng)窗口中0的個(gè)數(shù)
max_ = 0
for i in range(len(A)):
sliding_window += 1 # 拓展窗口長(zhǎng)度
if nums0 < K: # 滑動(dòng)窗口中 0 的個(gè)數(shù)小于 K吏祸，只拓展窗口
if A[i] == 0:
nums0 += 1
elif nums0 == K:
if A[i] == 0: # 如果再有 0 出現(xiàn)，更新滑動(dòng)窗口
while A[begin] == 1: # 找到滑動(dòng)窗口中第1個(gè)0的位置
begin += 1
sliding_window -= 1
begin += 1 # 新滑動(dòng)窗口的起始位置
sliding_window -= 1
max_ = max(max_, sliding_window) # 更新最大長(zhǎng)度
return max_
問(wèn)題描述：【Sliding Window钩蚊、DP贡翘、Array】1052. Grumpy Bookstore Owner
解題思路：
方法1（暴力 O(N^2)，TLE）：
- 根據(jù) customers 和 grumpy 數(shù)組砰逻，可以統(tǒng)計(jì)出不使用 X 技巧能得到的一個(gè)初始的滿意度總和鸣驱；
- 再考慮使用 X 技巧，對(duì)于每個(gè)位置蝠咆，將長(zhǎng)度為 X 的窗口中 grupmy[i] == 1 的 custpmers[i] 也加入到初始滿意度中踊东，然后更新最大滿意度。
這樣刚操，時(shí)間復(fù)雜度為 O(N*X)闸翅，由于 X 也可能達(dá)到 N 的長(zhǎng)度級(jí)別，因此為 O(N^2)菊霜，超時(shí)缎脾。
方法2（DP O(N^2)，勉強(qiáng) AC）：
嘗試了一下動(dòng)態(tài)規(guī)劃占卧，雖然時(shí)間復(fù)雜度還是 O(N^2)，但勉強(qiáng) AC 了联喘。DP 思路如下：
- 用 dp1[N] 記錄不使用 X 技巧的累加初始滿意度华蜒，dp2[N] 記錄使用 X 技巧的最大滿意度，最后 dp2[-1] 就是答案豁遭；
- dp1[N] 的狀態(tài)轉(zhuǎn)移方程很容易
dp1[i] = (dp1[i-1] + customers[i-1]) if grumpy[i-1] == 0 else dp1[i-1]叭喜； - dp2[N] 的狀態(tài)轉(zhuǎ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蓖谢，則老板不會(huì)生氣捂蕴，dp[i] 直接在 dp2[i-1] 的基礎(chǔ)上加上 customers[i-1] 就好；如果 grumpy[i-1] 為 1闪幽，則老板生氣啥辨，dp2[i] 的值取決于 dp2[i-1] （前面已經(jīng)生過(guò)氣）和 dp1[i-X] + sum(customers[i-X:i]) （當(dāng)前生氣，最大滿意度為前 dp1[i-X] 和這段 X 長(zhǎng)度大小的窗口中的數(shù)字之和）的最大值盯腌。 - 初始時(shí) dp[i] 中 i < X溉知，無(wú)論生氣與否，
dp2[i] = dp2[i-1] + customers[i-1]，因?yàn)?X 技巧可以充分展現(xiàn)级乍。
但是舌劳，實(shí)際上這種做法還是 O(N*X) 的時(shí)間復(fù)雜度，但是竟然勉強(qiáng) AC 了（可能臉好吧）玫荣。
Python3 實(shí)現(xiàn)（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）：
這也是一道經(jīng)典的利用滑動(dòng)窗口解決問(wèn)題的題目。
我們來(lái)定義本題的滑動(dòng)窗口：因?yàn)榭隙ó?dāng)技能 X 發(fā)揮時(shí)能獲得的滿意度最大捅厂，且這個(gè)窗口是連續(xù)的贯卦，因此窗口的大小是固定的。長(zhǎng)度為 X 的滑動(dòng)窗口中記錄增加的滿意度恒傻。
- 先求出不使用 X 技巧的初始滿意度脸侥；
- 因?yàn)榇翱谥杏涗浭褂?X 技巧增加的滿意度，所以它等于窗口中 grumpy[i] 為 1 的所有 customers[i] 之和盈厘；
- 窗口每次都向右移動(dòng)一位睁枕，剛開(kāi)始窗口大小小于 X，那么只要是 grumpy[i] == 1 就增加滿意度（因?yàn)榭梢猿浞职l(fā)揮 X 技巧）沸手；當(dāng)窗口大小等于 X 時(shí)外遇，滑動(dòng)過(guò)程中始終保持 X 長(zhǎng)度；
- 當(dāng)窗口大小等于 X契吉，如果出現(xiàn)一個(gè) grumpy[j] == 1跳仿，則窗口增加滿意度 customers[j]；同時(shí)捐晶，如果移出去的 grumpy[j-X] == 1菲语，那么滑動(dòng)窗口的滿意度要減去滿意度 customers[j-X]；
- 每次移動(dòng)窗口惑灵，都更新使用 X 技巧增加的滿意度的最大值山上；
- 最后，初始滿意度加上使用 X 技巧增加的滿意度的最大值就是總的最大滿意度英支。
這樣佩憾，時(shí)間復(fù)雜度為 O(N)。
Python3 實(shí)現(xiàn)（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的滑動(dòng)窗口中保存增加的滿意度
add_satisfied = 0 # 大小為X的滑動(dòng)窗口中增加的滿意度的最大值
for i in range(N):
if i < X and grumpy[i] == 1: # 沒(méi)有達(dá)到窗口大小
sliding_window += customers[i]
elif i >= X:
if grumpy[i] == 1:
sliding_window += customers[i] # 滑動(dòng)窗口中增加當(dāng)前滿意度
if grumpy[i-X] == 1:
sliding_window -= customers[i-X] # 滑動(dòng)窗口移除滿意度
add_satisfied = max(add_satisfied, sliding_window)
return initial_satisfied + add_satisfied # 兩者之和為最終滿意度
