0%

生成窗口最大值数组

发表于 更新于 分类于

生成窗口最大值数组算法

题目:

有一个整型数组arr和一个大小为w的窗口从数组的最左边滑倒最右边, 窗口每次都向右边滑一个位置. 例如, 数组为[4, 3, 5, 4, 3, 3, 6, 7], 窗口大小为3时, 窗口的最大值分别为: 5, 5, 5, 4, 6, 7. 如果数组长度为n, 窗口大小为w, 则一共产生n-w+1个窗口的最大值.

请实现一个函数.

  • 输入: 整型数组arr, 窗口大小为w.
  • 输出: 一共长度为n-w+1的数组res, res[i]表示每一种窗口状态下的最大值.

思路:

  • 使用双端队列来记录窗口的最大值

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector<int> get_max_window(vector<int>& arr, int w)
{
	vector<int> res;
	deque<int> max_index;
	for (int i = 0; i < arr.size(); ++i)
	{
		while (!max_index.empty() && arr[max_index.front()] <= arr[i])
		{
			max_index.pop_front();
		}
		max_index.push_back(i);
		if (max_index.front() == i - w)
		{
			max_index.pop_front();
		}
		if (i >= w - 1)
		{
			res.push_back(arr[max_index.front()]);
		}
	}
	return res;
}

题目: 最大值减去最小值小于或等于num的子数组数量

  • 给定数组arr和整数num, 共返回有多少个子数组满足如下情况:
    1. max(arr[i..j]) - min(arr[i..j]) <= m
    2. max(arr[i..j])代表子数组i到j上的最大值
    3. min(arr[i..j])代表子数组i到j上的最小值
  • 要求: 如果数组长度为N, 请实现时间复杂度为O(N)的解法

代码:

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
int get_num(vector<int>& arr, int num)
{
	deque<int> max_index, min_index;
	int res = 0, i = 0, j = 0;
	while (i < arr.size())
	{
		if (j < arr.size())
		{
			while (!max_index.empty() && arr[max_index.back()] <= arr[j])
			{
				max_index.pop_back();
			}
			max_index.push_back(j);
			while (!min_index.empty() && arr[min_index.back()] >= arr[j])
			{
				min_index.pop_back();
			}
			min_index.push_back(j);
		}
		if (arr[max_index.front()] - arr[min_index.front()] <= num && j < arr.size())
		{
			j++;
		}
		else
		{
			if (min_index.front() == i)
			{
				min_index.pop_front();
			}
			if (max_index.front() == i)
			{
				max_index.pop_front();
			}
			res += (j - i);
			i++;
		}
	}
	return res;
}