發現滑動窗口也是一種經典解題思路,這一篇簡單聊一下滑動窗口。
通常在碰到求XX子數組,子字符串,連續XX等題眼,可以考試用滑動窗口的思路來解決問題。
窗口的類型有幾種:
1. 固定長度的窗口。
2. 窗口大小未知,求最大/最小長度的窗口。
不管是可變窗口還是固定窗口,核心思路需要指定左右指針 left 和 right。
核心思路是:
1. left = 0, 窗口的起點默認是數組的起點。
2. right 根據條件初始化,即 right - left + 1 為窗口大小(固定窗口) 或者是 right = 0(可變窗口)
3. 每一次循環中left 和 right 同時移動(固定窗口),只移動 right,只有當left滿足條件時才移動(可變窗口)
4. 每次循環都判斷當前窗口內的元素是否滿足要求,如果是求最優解,可以繼續循環直到得到最優解。
舉個例子(https://leetcode-cn.com/problems/longest-subarray-of-1s-after-deleting-one-element/)
給你一個二進制數組 nums ,你需要從中刪掉一個元素。
請你在刪掉元素的結果數組中,返回最長的且只包含 1 的非空子數組的長度。
如果不存在這樣的子數組,請返回 0 。
標準的滑動窗口的題目,而且是可變窗口!從核心思路來看,就是 left 和 right 初始化為0,根據條件變更 left 和 right 的位置。
class Solution {
public int longestSubarray(int[] nums) {
int res = 0, sum = 0;
int left = 0;
for(int right = 0;right<nums.length;right++){
sum += (nums[right]&1);
while(left<right && sum <= right - left-1){
if(nums[left]==1) sum--;
left++;
}
res = Math.max(res,right-left);
}
return res;
}
}
浙公網安備 33010602011771號