前言科普：什么是滑動(dòng)窗口算法

滑動(dòng)問(wèn)題包含一個(gè)滑動(dòng)窗口，它是一個(gè)運(yùn)行在一個(gè)大數(shù)組上的子列表，該數(shù)組是一個(gè)底層元素集合。

假設(shè)有數(shù)組 [a b c d e f g h ]，一個(gè)大小為 3 的 滑動(dòng)窗口 在其上滑動(dòng)，則有：

[a b c]
 [b c d]
 [c d e]
  [d e f]
  [e f g]
   [f g h]

一般情況下就是使用這個(gè)窗口在數(shù)組的 合法區(qū)間 內(nèi)進(jìn)行滑動(dòng)，同時(shí) 動(dòng)態(tài)地 記錄一些有用的數(shù)據(jù)，很多情況下，能夠極大地提高算法地效率。

1. 滑動(dòng)窗口最大值

題目來(lái)源于 LeetCode 上第 239 號(hào)問(wèn)題：滑動(dòng)窗口最大值。題目難度為 Hard，目前通過(guò)率為 40.5% 。

題目描述

給定一個(gè)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口 k 內(nèi)的數(shù)字?；瑒?dòng)窗口每次只向右移動(dòng)一位。

返回滑動(dòng)窗口最大值。

示例:

輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7]

解釋:

  滑動(dòng)窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

題目解析

利用一個(gè) 雙端隊(duì)列，在隊(duì)列中存儲(chǔ)元素在數(shù)組中的位置， 并且維持隊(duì)列的嚴(yán)格遞減,，也就說(shuō)維持隊(duì)首元素是 最大的 ，當(dāng)遍歷到一個(gè)新元素時(shí), 如果隊(duì)列里有比當(dāng)前元素小的，就將其移除隊(duì)列，以保證隊(duì)列的遞減。當(dāng)隊(duì)列元素位置之差大于 k，就將隊(duì)首元素移除。

補(bǔ)充：什么是雙端隊(duì)列（Dqueue）

Deque 的含義是 “double ended queue”，即雙端隊(duì)列，它具有隊(duì)列和棧的性質(zhì)的數(shù)據(jù)結(jié)構(gòu)。顧名思義，它是一種前端與后端都支持插入和刪除操作的隊(duì)列。

Deque 繼承自 Queue（隊(duì)列），它的直接實(shí)現(xiàn)有 ArrayDeque、LinkedList 等。

動(dòng)畫(huà)描述

代碼實(shí)現(xiàn)

class Solution {
 public int[] maxSlidingWindow(int[] nums, int k) {
  //有點(diǎn)坑，題目里都說(shuō)了數(shù)組不為空，且 k > 0。但是看了一下，測(cè)試用例里面還是有nums = [], k = 0，所以只好加上這個(gè)判斷
  if (nums == null || nums.length < k || k == 0) return new int[0];
  int[] res = new int[nums.length - k + 1];
  //雙端隊(duì)列
  Deque<Integer> deque = new LinkedList<>();
  for (int i = 0; i < nums.length; i++) {
   //在尾部添加元素，并保證左邊元素都比尾部大
   while (!deque.isEmpty() && nums[deque.getLast()] < nums[i]) {
    deque.removeLast();
   }
   deque.addLast(i);
   //在頭部移除元素
   if (deque.getFirst() == i - k) {
    deque.removeFirst();
   }
   //輸出結(jié)果
   if (i >= k - 1) {
    res[i - k + 1] = nums[deque.getFirst()];
   }
  }
  return res;
  }
}

2. 無(wú)重復(fù)字符的最長(zhǎng)子串

題目來(lái)源于 LeetCode 上第 3 號(hào)問(wèn)題：無(wú)重復(fù)字符的最長(zhǎng)子串。題目難度為 Medium，目前通過(guò)率為 29.0% 。

題目描述

給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。

示例 1:

輸入: "abcabcbb"
輸出: 3
解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。
題目解析
建立一個(gè)256位大小的整型數(shù)組 freg ，用來(lái)建立字符和其出現(xiàn)位置之間的映射。

維護(hù)一個(gè)滑動(dòng)窗口，窗口內(nèi)的都是沒(méi)有重復(fù)的字符，去盡可能的擴(kuò)大窗口的大小，窗口不停的向右滑動(dòng)。

（1）如果當(dāng)前遍歷到的字符從未出現(xiàn)過(guò)，那么直接擴(kuò)大右邊界；
（2）如果當(dāng)前遍歷到的字符出現(xiàn)過(guò)，則縮小窗口（左邊索引向右移動(dòng)），然后繼續(xù)觀察當(dāng)前遍歷到的字符；
（3）重復(fù)（1）（2），直到左邊索引無(wú)法再移動(dòng)；
（4）維護(hù)一個(gè)結(jié)果res，每次用出現(xiàn)過(guò)的窗口大小來(lái)更新結(jié)果 res，最后返回 res 獲取結(jié)果。

動(dòng)畫(huà)描述

代碼實(shí)現(xiàn)

// 滑動(dòng)窗口
// 時(shí)間復(fù)雜度: O(len(s))
// 空間復(fù)雜度: O(len(charset))
class Solution {
public:
 int lengthOfLongestSubstring(string s) {
  int freq[256] = {0};
  int l = 0, r = -1; //滑動(dòng)窗口為s[l...r]
  int res = 0;
  // 整個(gè)循環(huán)從 l == 0; r == -1 這個(gè)空窗口開(kāi)始
  // 到l == s.size(); r == s.size()-1 這個(gè)空窗口截止
  // 在每次循環(huán)里逐漸改變窗口, 維護(hù)freq, 并記錄當(dāng)前窗口中是否找到了一個(gè)新的最優(yōu)值
  while(l < s.size()){
   if(r + 1 < s.size() && freq[s[r+1]] == 0){
    r++;
    freq[s[r]]++;
   }else { //r已經(jīng)到頭 || freq[s[r+1]] == 1
    freq[s[l]]--;
    l++;
   }
   res = max(res, r-l+1);
  }
  return res;
 }
};

3. 存在重復(fù)元素 II

題目來(lái)源于 LeetCode 上第 219 號(hào)問(wèn)題：存在重復(fù)元素 II。題目難度為 Easy，目前通過(guò)率為 33.9% 。

題目描述

給定一個(gè)整數(shù)數(shù)組和一個(gè)整數(shù) k，判斷數(shù)組中是否存在兩個(gè)不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的絕對(duì)值最大為 k。

示例 1:

輸入: nums = [1,2,3,1], k = 3
輸出: true

示例 2:

輸入: nums = [1,0,1,1], k = 1
輸出: true

示例 3:

輸入: nums = [1,2,3,1,2,3], k = 2
輸出: false

題目解析

使用用滑動(dòng)窗口與查找表來(lái)解決。

• 設(shè)置查找表record，用來(lái)保存每次遍歷時(shí)插入的元素，record的最大長(zhǎng)度為k
• 遍歷數(shù)組nums，每次遍歷的時(shí)候在record查找是否存在相同的元素，如果存在則返回true，遍歷結(jié)束
• 如果此次遍歷在record未查找到，則將該元素插入到record中，而后查看record的長(zhǎng)度是否為k + 1
• 如果此時(shí)record的長(zhǎng)度是否為k + 1，則刪減record的元素，該元素的值為nums[i - k]
• 如果遍歷完整個(gè)數(shù)組nums未查找到則返回false
  

代碼實(shí)現(xiàn)

// 時(shí)間復(fù)雜度: O(n)
// 空間復(fù)雜度: O(k)
class Solution {
public:
 bool containsNearbyDuplicate(vector<int>& nums, int k) {
  if(nums.size() <= 1) return false;
  if(k <= 0) return false;
  unordered_set<int> record;
  for(int i = 0 ; i < nums.size() ; i ++){
   if(record.find(nums[i]) != record.end()){
    return true;
   }
   record.insert(nums[i]);
   // 保持record中最多有k個(gè)元素
   // 因?yàn)樵谙乱淮窝h(huán)中會(huì)添加一個(gè)新元素,使得總共考慮k+1個(gè)元素
   if(record.size() == k + 1){
    record.erase(nums[i - k]);
   }
  }
  return false;
 }
};

4. 長(zhǎng)度最小的子數(shù)組

題目來(lái)源于 LeetCode 上第 209 號(hào)問(wèn)題：長(zhǎng)度最小的子數(shù)組。題目難度為 Medium，目前通過(guò)率為 37.7% 。

題目描述

給定一個(gè)含有 n 個(gè)正整數(shù)的數(shù)組和一個(gè)正整數(shù) s ，找出該數(shù)組中滿(mǎn)足其和 ≥ s 的長(zhǎng)度最小的連續(xù)子數(shù)組。如果不存在符合條件的連續(xù)子數(shù)組，返回 0。

示例:

輸入: s = 7, nums = [2,3,1,2,4,3]
輸出: 2
解釋: 子數(shù)組 [4,3] 是該條件下的長(zhǎng)度最小的連續(xù)子數(shù)組。

題目解析

定義兩個(gè)指針 left 和 right ，分別記錄子數(shù)組的左右的邊界位置。

（1）讓 right 向右移，直到子數(shù)組和大于等于給定值或者 right 達(dá)到數(shù)組末尾；
（2）更新最短距離，將 left 像右移一位, sum 減去移去的值；
（3）重復(fù)（1）（2）步驟，直到 right 到達(dá)末尾，且 left 到達(dá)臨界位置

動(dòng)畫(huà)描述

設(shè)置滑動(dòng)窗口的長(zhǎng)度為 0 ，位于數(shù)軸的最左端。

1 .滑動(dòng)窗口右端 R 開(kāi)始移動(dòng)，直到區(qū)間滿(mǎn)足給定的條件，也就是和大于 7 ，此時(shí)停止于第三個(gè)元素 2，當(dāng)前的最優(yōu)長(zhǎng)度為 4

圖 1

2. 滑動(dòng)窗口左端 L 開(kāi)始移動(dòng)，縮小滑動(dòng)窗口的大小，停止于第一個(gè)元素 3，此時(shí)區(qū)間和為 6，使得區(qū)間和不滿(mǎn)足給定的條件（此時(shí)不大于 7）

圖片 2

3. 滑動(dòng)窗口右端 R 繼續(xù)移動(dòng)，停止于第四個(gè)元素 4，此時(shí)和位 10 ，但最優(yōu)長(zhǎng)度仍然為 4

圖片 3

代碼實(shí)現(xiàn)

// 滑動(dòng)窗口的思路
// 時(shí)間復(fù)雜度: O(n)
// 空間復(fù)雜度: O(1)
class Solution {
 public int minSubArrayLen(int s, int[] nums) {
  int l= 0,r = -1; // nums[l...r]為我們的滑動(dòng)窗口
  int sum = 0;
  int result = nums.length + 1;
  while (l < nums.length){ // 窗口的左邊界在數(shù)組范圍內(nèi),則循環(huán)繼續(xù)

   if( r+1 <nums.length && sum < s){
    r++;
    sum += nums[r];
   }else { // r已經(jīng)到頭 或者 sum >= s
    sum -= nums[l];
    l++;
   }

   if(sum >= s){
    result = (r-l+1) < result ? (r-l+1) : result ;
   }
  }
  if(result==nums.length+1){
   return 0;
  }
  return result;
 }
}

總結(jié)

以上所述是小編給大家介紹的分享幾道和「滑動(dòng)窗口」有關(guān)的算法面試題,希望對(duì)大家有所幫助，如果大家有任何疑問(wèn)請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！
如果你覺(jué)得本文對(duì)你有幫助，歡迎轉(zhuǎn)載，煩請(qǐng)注明出處，謝謝！

最新評(píng)論