lcMovingWindow - 滑动窗口 1

Posted on Edited on

1 滑动窗口

priority_queue经常用

0480 滑动窗口中位数

1 题目

https://leetcode-cn.com/problems/sliding-window-median/

2 解题思路

  • 1 使用一个multiset维护当前窗口，
    • 1.1 不使用priority_queue的原因，无法删除元素
    • 1.2 不使用map/set的原因，不能含有重复元素
  • 2 对于窗口，维护一个中位数指针，注意到中位数指针在每一次窗口移动只会发生几种情况
    • 2.1 向左，向右，不动
    • 2.2 分类讨论清除即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        long long n = nums.size();
        std::multiset<long long, std::less<long long>> mySet(nums.begin(), nums.begin() + k);

        vector<double> res;
        multiset<long long>::iterator mid = mySet.begin();
        std::advance(mid, (k-1)/2);

        for(long long i = k; i <= n; ++i) {
            res.emplace_back((*mid + *next(mid, 1 - k%2))*1.0L/2);
            if(i == n) break;

            mySet.insert(nums[i]);
            if (nums[i] > *mid && nums[i - k] < *mid) {
                mid++;
                mySet.erase(mySet.lower_bound(nums[i-k]));
                continue;
                // std::advance(mid, 1);
            }

            if (nums[i] < *mid && nums[i - k] > *mid) {
                mid--;
                mySet.erase(mySet.lower_bound(nums[i-k]));
                continue;
                // std::advance(mid, -1);
            }
            // 7 3 7 7 4, k = 4
            // 7 8 7 7 4, k = 4
            if(nums[i-k] == *mid) {
                if(nums[i] >= *mid)  ++mid;
                else {
                    if(*prev(mid) != *mid) {
                        --mid;
                    }
                }
                mySet.erase(mySet.lower_bound(nums[i-k]));
                continue;
            } 

            if(nums[i] == *mid) {// 相当于一个比mid大的数字插入到了mid的前面
                if(nums[i-k] <= *mid)  ++mid;
                mySet.erase(mySet.lower_bound(nums[i-k]));
                continue;
            }
        }
        return res;
    }
};

0992 k个不同元素的子数组个数

1 题目

https://leetcode-cn.com/problems/subarrays-with-k-different-integers/submissions/

2 解题思路

  • 1 正常思路：
    • 1.1 首先窗口是必须的，即为[st, ed]，那么保证这个窗口时刻含有k个不同变量，然后求出来每个以ed为结尾的子数组的个数求和即可
    • 1.2 那么以ed为结尾的窗口[st, ed]的子数组个数求法，假设k=2，窗口为1,2，1,2,那么以ed为结尾，st就向前移动，直到窗口内的不同元素个数减少到了k-1，此时st移动到第二个2的位置，一共移动了3次，也就是说以ed为结尾的含有k个不同变量的子数组个数为3。
    • 1.3 其中的复杂之地在于：如何判断窗口内不同元素的个数，我们采用经典的空间换时间的方法(因为所有元素的值不会大于数组本身长度),用freq[val]记录val出现的次数， 倘若长度不限呢？那就需要使用unordered_map来记录当前窗口所有元素的出现次数，然后每移动一次st需要遍历一遍这个map来判断当前窗口内不同元素的个数，那么整体复杂度为： o(n * k * k)
  • 2 官方题解：
    • 2.1 不同元素为k的子数组的个数为： 不同元素最多为k的子数组个数 - 不同元素最多为k-1的子数组个数，那么问题转为求不同元素最多为k的一个数组它子数组的个数
    • 2.2 求法： 还是滑动窗口的思想，始终保持窗口中最多元素的个数不超过k（方式为每次移动ed，直到第一次超过k，然后移动st直到小于k），然后对于每个ed，ed - st就是以ed为窗口结尾对应的不同元素不超过k的子数组的个数，举个例子：(官方例子)：

      用具体的例子理解：最多包含 3 种不同整数的子区间 [1, 3, 2, 3] （双指针算法是在左边界固定的前提下，让右边界走到最右边），当前可以确定 1 开始的满足最多包含 3 种不同整数的子区间有 [1]、[1, 3]、[1, 3, 2]、[1, 3, 2, 3]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        return maxSubArrayNumForKDiff(nums, k) - maxSubArrayNumForKDiff(nums, k - 1);

    }

    int maxSubArrayNumForKDiff(vector<int>& nums, int k) {
        vector<int> freq(nums.size() + 1);
        long long res = 0;
        int st = 0;
        int ed = 0;
        int curCnt = 0;
        while(ed < nums.size()) {
            // 求每个ed对应得到的最多k个不同元素的子数组个数
            if(freq[nums[ed]] == 0) {
                curCnt ++;
            }
            freq[nums[ed]]++;
            ++ed;

            // 减小窗口到窗口内元素种类第一次为k-1个
            while(curCnt > k) {
                freq[nums[st]]--;
                if(freq[nums[st]] == 0) {
                    curCnt--;
                }
                ++st;
            }
            res += ed - st;
        }
        return res;
    }
};

0904 完全水果个数

1 题目

https://leetcode-cn.com/problems/fruit-into-baskets/

2 解题思路

  • 1 正常思路：(于0904https://leetcode-cn.com/problems/fruit-into-baskets/实现)
    • 1.1 首先窗口是必须的，即为[st, ed]，那么保证这个窗口时刻含有k个不同变量，然后求出来每个以ed为结尾的子数组的个数求和即可
    • 1.2 那么以ed为结尾的窗口[st, ed]的子数组个数求法，假设k=2，窗口为1,2，1,2,那么以ed为结尾，st就向前移动，直到窗口内的不同元素个数减少到了k-1，此时st移动到第二个2的位置，一共移动了3次，也就是说以ed为结尾的含有k个不同变量的子数组个数为3。
    • 1.3 其中的复杂之地在于：如何判断窗口内不同元素的个数，我们采用经典的空间换时间的方法(因为所有元素的值不会大于数组本身长度),用freq[val]记录val出现的次数， 倘若长度不限呢？那就需要使用unordered_map来记录当前窗口所有元素的出现次数，然后每移动一次st需要遍历一遍这个map来判断当前窗口内不同元素的个数，那么整体复杂度为： o(n * k * (log k)) = o(n)
  • 2 官方题解：
    • 2.1 不同元素为k的子数组的个数为： 不同元素最多为k的子数组个数 - 不同元素最多为k-1的子数组个数，那么问题转为求不同元素最多为k的一个数组它子数组的个数
    • 2.2 求法： 还是滑动窗口的思想，始终保持窗口中最多元素的个数不超过k（方式为每次移动ed，直到第一次超过k，然后移动st直到小于k），然后对于每个ed，ed - st就是以ed为窗口结尾对应的不同元素不超过k的子数组的个数，举个例子：(官方例子)：

      用具体的例子理解：最多包含 3 种不同整数的子区间 [1, 3, 2, 3] （双指针算法是在左边界固定的前提下，让右边界走到最右边），当前可以确定 1 开始的满足最多包含 3 种不同整数的子区间有 [1]、[1, 3]、[1, 3, 2]、[1, 3, 2, 3]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        if(fruits.size() <= 1) {
            return 1;
        }

        // 不同元素最多为2的数组长度
        int res = 0;
        int st = 0;
        int ed = 0;
        int curCnt = 0;
        map<int, int> freq;
        bool stNotMov = true;
        while(ed < fruits.size()) {
            while(freq.size() <= 2 && ed < fruits.size()) {
                if(freq.find(fruits[ed]) == freq.end()) {
                    curCnt++;
                }
                freq[fruits[ed]]++;
                ed++;
            }
            
            if(!stNotMov && ed != fruits.size()) {
                res = std::max(res, ed - st - 1);
            } else  {
                if(freq.size() == 3) {
                    res = std::max(res, ed - st - 1);
                } else {
                    res = std::max(res, ed - st);
                }
                
            }
            
            while(freq.size() > 2) {
                freq[fruits[st]]--;
                if(freq[fruits[st]] == 0) {
                    freq.erase(freq.find(fruits[st]));
                }
                ++st;
                stNotMov = false;
            }
        }
        return res;
    }
};

0995 执行次数最小: 每次翻转k个让数组全为1

1 题目

https://leetcode-cn.com/problems/minimum-number-of-k-consecutive-bit-flips/

2 解题思路

  • 1 正常思路：窗口始终保持k个，去模拟翻转过程，由于需要在窗口内找到翻转后第一个为0的数字，这个复杂度为O（k），所以总复杂度为： O(n*k)
  • 2 官方题解：使用差分数组diff,diff[i]表示nums[i]比nums[i-1]多了多少次翻转，那么当前总的翻转次数就为： sum(diff[i])，对于nums[i]而言， sum(diff[i])%2为0则表示nums[i]需要翻转。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k) {
        vector<long long> preSum = {0};
        for(long long num : nums) {
            preSum.emplace_back(preSum.back() + num);
        }

        long long st = 0;
        long long ed = st + k - 1;
        long long n = nums.size();
        long long res = 0;

        vector<long long> diff(n+1);
        long long flipCnt = 0;
        // while(st < n - k + 1) {
            // 模拟思路会超时
            // if(nums[st] == 1) {
            //     ++st;
            //     continue;
            // }
            // int newSt = flipKBit(nums, k, st, preSum);
            // if(newSt == -1) {
            //     st = st + k;
            // } else {
            //     st = newSt;
            //     res += 1;
            // }
        // }
        // if(find(nums.end() - k, nums.end(), 0) == (nums.end())) {
        //     return res;
        // } 

        while(st < n) {
            // 采用查分数组记录每个元素应该翻转的次数
            // 这启发我们用差分数组的思想来计算当前数字需要翻转的次数。我们可以维护一个差分数组 \textit{diff}diff，其中 \textit{diff}[i]diff[i] 表示两个相邻元素 
            // \textit{nums}[i-1]nums[i−1] 和 \textit{nums}[i]nums[i] 的翻转次数的差，对于区间 [l,r][l,r]，将其元素全部加 11，只会影响到 ll 和 r+1r+1 处的差分值，
            // 故 \textit{diff}[l]diff[l] 增加 11，\textit{diff}[r+1]diff[r+1] 减少 11。
            flipCnt += diff[st];
            if((flipCnt + nums[st]) % 2 == 0) {
                if(st + k > n) {
                    return -1;
                }
                diff[st] ++;
                diff[st + k] --;
                res++;
                flipCnt ++;
            }
            ++st;
        }
        return res;
    }

    // 翻转kbit，返回第一个翻转窗口中反转后值不等于1的下标，否则返回-1
    int flipKBit(vector<int>& nums, int k, int st, vector<int>& preSum) {
        int firstNot1 = INT_MAX;
        // 需要O(k)时间的复杂度
        bool needFlip = find(nums.begin() + st, nums.begin() + st + k, 0) != (nums.begin() + st + k);
        // 使用前缀和优化，由于实地翻转了数组，于是会改变对应的前缀和，所以此方法行不通
        // bool needFlip = ((preSum[st + k] - preSum[st]) != k);

        // for(int i = st; i < k; ++i) {
        //     if(nums[st + i] != 1) {
        //         needFlip = true;
        //     }
        // }
        if(needFlip) {
            for(int i = 0; i < k; ++i) {
                nums[st + i] = abs(nums[st + i] - 1);
                if(nums[st + i] != 1) {
                    firstNot1 = min(firstNot1, st + i);
                }
            }
            return firstNot1 > nums.size() ? st + k : firstNot1 ;
        }
        

        return -1;
    }
};

1696 最大结果

1 题目

https://leetcode-cn.com/problems/jump-game-vi/submissions/

2 解题思路

  • 1 采用动态规划：dp[i]表示跳到i处的最大收益,如下：搜索i的前k个下标即可
    1
    2
    3
    4
    5
    6
    7
    8
    // o(n * k)解法
    dp[0] = 0;
    dp[1] = nums[0];
    for(int i = 1; i < nums.size() + 1; ++i) {
        for(int m = 1; m < k + 1 && i - m > 0; ++m) {
            dp[i] = max(dp[i], dp[i-m] + nums[i-1]);
        }
    }
  • 2 优化上述搜索前k个下标的方案，我们采用优先队列来维护前k个中最大的上一跳：
    • 将上述O(n*k)变为O(n*logk)，原因是maxHeap的push操作是logN的复杂度
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      class Solution {
      public:
          struct number {
              long long idx = 0;
              long long val = 0;
              number(long long idx, long long val): idx(idx), val(val) {};

              // sort descending
              bool  operator<(const number& b) const {return this->val < b.val;}
          };
          int maxResult(vector<int>& nums, int k) {
              vector<long long> dp(nums.size() + 1, INT_MIN);
              // o(n * k)解法
              dp[0] = 0;
              dp[1] = nums[0];
              // for(int i = 1; i < nums.size() + 1; ++i) {
              //     for(int m = 1; m < k + 1 && i - m > 0; ++m) {
              //         dp[i] = max(dp[i], dp[i-m] + nums[i-1]);
              //     }
              // }

              std::priority_queue<number, std::vector<number>, std::less<number>> maxHeap;
              maxHeap.push({1, nums[0]});
              // 使用堆优化：
              for(int i = 2; i < nums.size() + 1; ++i) {
                  while(maxHeap.top().idx < i - k) {
                      maxHeap.pop();
                  }

                  dp[i] =  maxHeap.top().val + nums[i - 1];
                  maxHeap.push({i, dp[i]});
                  
                  // for(int m = 1; m < k + 1 && i - m > 0; ++m) {
                  //     dp[i] = max(dp[i], dp[i-m] + nums[i-1]);
                  // }
              }
              
              return dp[nums.size()];

          }
      };

总结

滑动窗口的最大值：可以使用maxHeap来维护，复杂度logk