小羊的學習筆記Sliding Window
2023/10/20
本篇會以已經知道 Sliding Window 來做介紹，這邊只會整理題目跟分享解題心得，如果還沒有學過的人請先去找資源學習。
基本上 Sliding Window 的題目幾乎都是可以很簡單暴力解的題目，而使用 Sliding Window 可以避免不必要的重複計算，優化時間複雜度。
題目整理
基礎題型
應用題組
這邊是我覺得很適合在面試的時候考的類型，從 easy 題延伸到 medium，很容易包裝，而且前兩題都是非常簡單的邏輯題而已。
經典題組
- 485. Max Consecutive Ones
- 487. Max Consecutive Ones II 這題要訂閱 Leetcode Premium 才可以看，不過其實就是第一題延伸，有一次機會將其中一個 0 換成 1，一樣求最長連續
1的數量。 - 1004. Max Consecutive Ones III
第一題解答
javascript
function findMaxConsecutiveOnes(nums) {
let max = 0;
let count = 0;
for (const num of nums) {
if (num === 1) count++;
else count = 0;
max = Math.max(max, count);
}
return max;
}
第二題解答
javascript
function longestOnes(nums) {
let max = 0;
let leftCount = 0;
let rightCount = 0;
for (const num of nums) {
rightCount++;
if (num === 0) {
leftCount = rightCount;
rightCount = 0;
}
max = Math.max(max, leftCount + rightCount);
}
return max;
}
紀錄 0 左右的 1 數量，當然也可以直接用第三題的方式解，就是把 k 改成 1 而已
第三題解答
javascript
function longestOnes(nums, k) {
let max = 0;
let count = 0;
let zeroCount = 0;
for (let i = 0; i < nums.length; i++) {
count++;
if (nums[i] === 0) {
zeroCount++;
while (zeroCount > k) {
count--;
if (nums[i - count] === 0) zeroCount--;
}
}
max = Math.max(max, count);
}
return max;
}
使用 sliding window 的概念 按照順序遍歷 array，使用 zeroCount 紀錄 0 的數量，當 0 的數量大於 k 時，就往前扣掉第一個 0 以前的所有 1。
這類型的題目可以包裝成各種應用題，比如 Max Consecutive Ones 系列題目。
可以包裝成以下問題：
- 有個人的工作是排班制的，他想知道今年的最長假期是多長，輸入一個班表的
array裡面只有0和1，0是放假日、1是上班日，請輸出最長連續假期天數。 - 延續上題，如果他有一天的特休可以使用，那他能得到的最長連假是多長？
- 延續上題，如果他有
k天的特休可以使用，那他能得到的最長連假是多長？
Sliding Window 包裝起來千變萬化，但其實解法都一模一樣，請一定要完全理解，盡量不要背答案，題目非常多也太不可能寫得完的，如果這種簡單的 coding 技巧題都要用背的，那等進到DP時應該會非常痛苦，不看答案永遠寫不出來。
變化延伸
這兩題不是題組而是獨立的題目，只是上面題組最後一題換包裝後的小變化。
搭配 Hash Table
String 類
很多 Sliding Window 的題目都會搭配 Hash Table