生成窗口最大值数组

1、生成窗口最大值数组

有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。

例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时：

[4 3 5] 4 3 3 6 7 窗口中最大值为5

4 [3 5 4] 3 3 6 7 窗口中最大值为5

4 3 [5 4 3] 3 6 7 窗口中最大值为5

4 3 5 [4 3 3] 6 7 窗口中最大值为4

4 3 5 4 [3 3 6] 7 窗口中最大值为6

4 3 5 4 3 [3 6 7] 窗口中最大值为7

如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。

请实现一个函数，给定一个数组arr，窗口大小w。

返回一个长度为n-w+1的数组res,res[i]表示每一种窗口状态下的最大值。以本题为例，结果应该返回[5,5,5,4,6,7]。

2、最大值减去最小值小于或等于num的子数组数量

给定数组arr和整数num，返回有多少个子数组满足如下情况:

max(arr[i..j]) - min(arr[i..j]) <= num

max(arr[i..j])表示子数组arr[i..j]中的最大值，min(arr[i..j])表示子数组arr[i..j]中的最小值。

如果数组长度为 N，请实现时间复杂度为 O(N)的解法。

参考代码如下：

 C++ Code ## 需要C++ 11支持 ##

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

#include <iostream>
#include <cmath>
#include <string.h>
#include <vector>
#include <deque>

using namespace std;

#define LENGTH(Arr) (sizeof(Arr) / sizeof(Arr[0]))

/** @brief
* 生成窗口最大值数组
* 实现一个函数，给定一个数组arr，窗口大小w。返回一个长度为n-w+1的数组res
* res[i]表示每一种窗口状态下的最大值
*
* @param arr[] int
* @param length int -数组长度
* @param winLen int -窗口大小
* @return vector<int> -最大值数组
*
*/
vector<int> SlidingWindowMaxArray(int arr[], int length, int winLen)
{
    deque<int> maxQueue; // 双端队列，存储下标，对应元素降序排列
    vector<int> ret; // 结果

    for(int i = 0; i < length; ++i)
    {
        /**< 若当前元素>=队列尾部元素，则队列尾出队列 */
        while(!maxQueue.empty() && arr[maxQueue.back()] <= arr[i])
        {
            maxQueue.pop_back();
        }
        maxQueue.push_back(i); // 当前元素下标进入队列尾部

        if(maxQueue.front() == i - winLen) // 当前窗口范围>w,则队列头部出队列
        {
            maxQueue.pop_front();
        }

        if(i >= winLen - 1) // 初始时可能窗口范围<w
        {
            ret.push_back(arr[maxQueue.front()]);
        }
    }

    return ret;
}

/** @brief
* 最大值减去最小值小于或等于num的子数组数量
* 给定数组arr和整数num，返回有多少个子数组满足如下情况:
* max(arr[i..j]) - min(arr[i..j]) <= num
*
* @param arr[] int
* @param length int
* @param num int
* @return int
*
*/
int AllLessNumSubArray(int arr[], int length, int num)
{
    deque<int> minDeque;
    deque<int> maxDeque;
    int ret = 0;
    int low = 0;
    int high = 0;
    while(low < length)
    {
        while(high < length)
        {
            while(!minDeque.empty() && arr[minDeque.back()] >= arr[high])
            {
                minDeque.pop_back();
            }
            minDeque.push_back(high);

            while(!maxDeque.empty() && arr[maxDeque.back()] <= arr[high])
            {
                maxDeque.pop_back();
            }
            maxDeque.push_back(high);

            if(arr[maxDeque.front()] - arr[minDeque.front()] > num) break;

            ++high;
        }

        if(minDeque.front() == low) minDeque.pop_front();
        if(maxDeque.front() == low) maxDeque.pop_front();

        ret += high - low;
        ++low;
    }

    return ret;
}

int main()
{
    int arr[] = {4, 3, 5, 4, 3, 3, 6, 7};
    for(auto val : SlidingWindowMaxArray(arr, LENGTH(arr), 3))
    {
        cout << val << " ";
    }
    cout << endl; // 输出结果【5 5 5 4 6 7】

    int arr1[] = {7, 9, 6, 1, 0,
                  7, 5, 4, 4, 4,
                  2, 0, 7, 1, 7,
                  2, 5, 3, 1, 9,
                  0, 8, 8, 9, 4,
                  2, 3, 6, 9, 8
                 };
    cout << AllLessNumSubArray(arr1, LENGTH(arr1), 5) << endl; // 79

    return 0;
}