【Hello Algorithm】滑动窗口内最大值最小值

滑动窗口介绍

滑动窗口是一种我们想象中的数据结构 它是用来解决算法问题的

我们可以想象出一个数组 然后再在这个数组的起始位置想象出两个指针 L 和 R

我们对于这两个指针做出以下规定

• L 和 R指针只能往右移动
• L指针不能走到R指针的右边
• 我们只能看到L指针和R指针中间的数字

比如说当前L和R指针重合 我们就什么数字都看不见

如果此时R指针往右走一步 那么我们就能看到L指针和R指针中间的数组的数字

又因为这种移动的方式特别像滑动 所以说我们将这种想象出来的数据结构叫做滑动窗口

如何确定一个滑动窗口内的最大值

如果我们每次都遍历去获取滑动窗口的最大值的话那么每次获取的时间复杂度就是O（N）了 这样子明显很复杂 所以说我们需要想想别的方式去找到最大值

这里直接给出结论：

• 我们使用双端队列去获取一个滑动窗口内的最大值
• 双端队列的意义是 ： 此时开始缩小滑动窗口 哪些数字可能成为最大值

为了让双端队列能够实现它的意义 我们做出以下规定

• 让R指针向右滑动的时候 我们从右边插入数字的下标到双端队列中
• 如果说插入的数字要大于原来的数字 我们让原来的数字出队列
• 让L指针向右滑动的时候 我们从左边开始比较双端队列第一个（左边数起）下标和L指针的下标
• 如果说L指针的下标要大于双端队列最左边的下标 则将其弹出

至于C++中的双端队列 大家可以参考这篇博客 双端队列

窗口内最大值

假设一个固定大小为W的窗口 依次划过数组arr

让你依次返回每次窗口移动时窗口中的最大值

假设数组arr为 【4 ， 3 ， 5 ，4， 3， 3， 6， 7】 W = 3

返回【5 ， 5， 5， 4， 6， 7】

---

这道题目实际上就是一个滑动窗口最大值的简单版本

我们使用一个双端队列就能很轻松的实现

面对这个问题我们可以拆分成两部分来解决

1. 首先把滑动窗口的大小扩大到3
2. 接着滑动窗口整体开始移动

两部分的代码都不算难 代码表示如下

void process5(vector<int>& arr , vector<int>& ans , int W)
{
  deque<int> dq(0  , 0);

  for (int R = 0; R < W; R++)
  {
    while (!dq.empty() && arr[dq.front()] <= arr[R])
    {
      dq.pop_back();
    }    
    
    dq.push_back(R);    
  }    
1
2
3
4
5
6
7
8
9
10
11
12
13

  int R = W - 1;    
  int L = 0;    
  int N = static_cast<int>(arr.size());    
  while (R < N)    
  {    
    while (!dq.empty() && arr[dq.back()] <= arr[R])                                                                                                                          { 
        dq.pop_back();
    }                     
         
    dq.push_back(R);
                                                                                                                                                                     
    while (L > dq.front())    
    {                         
       dq.pop_front();
    }                     
         
    ans.push_back(arr[dq.front()]);
    L++;    
    R++;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这道题目给我们的提醒主要有两个

1. 当我们R指针右移的时候要使用while来进行判断
2. R指针在初始化之后要重置 否则会出现一些错误 为了避免这些错误 我们最好每次使用一个变量之前对其进行初始化

子数组中符合条件的个数

给定一个整形数组arr 和一个整数num

某个arr中的子数组sub 必须要满足

sub中的最大值减去sub中的最小值小于等于num

返回sub中达标的子数组的数量

---

我们首先分析下问题

如果我们没有学过滑动窗口和双端队列 那么这道题我们会使用暴力的方式来得到答案

三个for循环嵌套 时间复杂度就变成了n的三次方 这显然是不可以的

当我们使用滑动窗口解决这个问题的时候 由于我们的左右两个下标都是单向的往右边移动 所以说此时的时间复杂度就是N

---

当我们得到两个下标满足上述条件时 比如说0 ~ N上的最大值减去0~N中的最小值小于等于num

此时我们就可以说 左下标为0 右下标为0 ~ N-1上的任意一个子数组都满足条件

因为此时最大值只有可能变小 最小值只有可能变大 所以说它们之间的差值肯定还是会小于等于num

所以我们就能确定 以0为左边界 N为右边界上符合条件的子数组有 N - 0 + 1个

之后我们左边界右移即可

---

整体思路如下

• 我们使用两个双端队列来记录子数组的最大值和最小值
• 我们让右边界一直右移动 直到子数组不满足条件为止
• 此时通过上面的技巧计算出左边界到右边界-1的满足条件子数组个数 之后左边界++

代码表示如下

int process(vector<int>& arr, int num)
{
    deque<int> Max_Win(0, 0);
    deque<int> Min_Win(0, 0);

    int count = 0;
    int R = 0;
    int N = static_cast<int>(arr.size());
    for (int L = 0; L < N; L++)
    {
        while (R < N)
        {
            while (!Max_Win.empty() && arr[Max_Win.back()] <= arr[R])
            {
                Max_Win.pop_back();
            }
            Max_Win.push_back(R);

            while (!Min_Win.empty() && arr[Min_Win.back()] >= arr[R])
            {
                Min_Win.pop_back();
            }
            Min_Win.push_back(R);

            if (arr[Max_Win.front()] - arr[Min_Win.front()] > num)
            {
                break;
            }
            else
            {
                R++;
            }

        }

        count += R - L;

        if (Max_Win.front() == L)
        {
            Max_Win.pop_front();
        }

        if (Min_Win.front() == L)
        {
            Min_Win.pop_front();
        }
    }

    return count;
}
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

这里有一点需要注意的是

 count += R - L;
1

语句必须要放到while循环的外面才行 否则会因为R下标越界的问题而导致不会执行if语句 最终导致count计算不完整

加油站的良好出发点问题

此时我们有两个数组 gas 和 cost

gas数组的意思每个加油点可以加多少单位的油

cost数组的意思是从当前加油点到下个加油点需要花费多少油（如果下个加油点不存在则视为是第一个加油点）

问题是 假设从其中任意一个加油点触发 起始车里没有油 能否跑完一圈？

---

我们可以稍微理解下这个问题 起始两个数组gas 和 cost 可以转化为一个 rest 数组

如果 rest 数组中有小于0的值则说明从该出发点无法跑通 如果没有则说明可以跑通

其实我们想到了这一层就应该能联想到要使用窗口内最小值来解这道题目了 但是这里又会出现一个新的问题 – 如果我们的起点不是从0下标开始的 那么整个数组就需要 “拐弯”

对于这个问题的解决方式是 我们可以将整个数组扩容到原来的双倍

根据原来的数组 我们可以建立一个新的数组并且将每个数组位置的含义变为汽车到该加油站时剩余的单位油量 超出原数组的部分我们从0下标开始再顺序循环一遍

这样子我们就可以使用滑动窗口来解决这个问题了 解决步骤如下

• 设置原数组的大小为窗口大小
• 每次窗口移时选取一个最小值

代码表示如下

void process(vector<int>& arr , int num , vector<int>& ans)
{
  deque<int> Min_Win(0 , 0);

  for (int R = 0; R < num ; R++)
  {
    while(!Min_Win.empty() && arr[Min_Win.back()] >= arr[R])
    {
      Min_Win.pop_back();
    }

    Min_Win.push_back(R);
  }                    
                        
  int R = num - 1;   
  int L = 0;        
  while (R < static_cast<int>(arr.size()))  
  {  
                                                             
   while(!Min_Win.empty() && arr[Min_Win.back()] >= arr[R])  
    {                         
        Min_Win.pop_back();  
    }                             
     
    Min_Win.push_back(R);                                     
       
    if (Min_Win.front() == L)  
    {  
      Min_Win.pop_front();  
    }                      
    L++;  
    R++;  
                    
    if (arr[Min_Win.front()] < 0)  
    {                                       
      ans.push_back(0);  
    }  
    else                                                         
    {      
      ans.push_back(1);                                                                                                                                                                                                                                             
    }                                                                                                                                  
  }                                                                                                                                                                                                                                                                          
}   
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

之后我们只需要对于vector里面的int类型数据进行判断 如果是0则不能到达 如果是1则可以到达

不过这里也有几个需要注意的问题

1. 我们不能使用 vector 来存储bool类型的数据
2. 在传入porcess函数之前我们需要对于数组进行加工
3. 每次使用L , R下标之前需要重置成我们希望的值 否则可能会出现一些问题

滑动窗口问题总结

当我们需要一段范围的最大值或者是最小值的时候 我们能够想到两种方式

• 堆排序
• 滑动窗口

而什么时候选择排序什么时候选择滑动窗口呢？

我们说 当数据的范围在不停的变化（这个变化要是线性的 不能是随机的）的时候 我们可以选择滑动窗口来解决我们的问题

当只有数据增加的时候我们可以选择使用堆排序来解决问题