【算法作业】连续序列的最大波谷

Uncategorized
1.8k words

问题描述

有一系列数，假设l-序列是其中长度为l的连续子序列，对于每个l-序列有一个最小值，称之为l-序列的波谷。设计算法策略求原序列中的最大波谷（max（min（l-序列））。

解题思路

读题： 这里的l是一个给定的值，不是变化的。(因为我一开始就搞错了)

方法一（暴力）：

设想弄个两层循环，第二层循环寻找l-序列中的最小值，很简单，时间复杂度为O($n * l$)

方法二（双端队列）：

  1. 在函数findMaxWave中，首先创建了一个双端队列 dq，用于存储元素的下标。

  2. 然后，算法通过两个循环分别处理前l个元素和剩余元素。

    • 在处理前l个元素时，通过一个循环遍历，并且使用一个while循环保持队列中的元素按照递减的顺序排列。具体来说，如果当前元素比队列中的最后一个元素小或等于，则将队列中的最后一个元素移除，直到队列为空或者当前元素大于队列中的最后一个元素，然后将当前元素的下标加入队列中。

    • 在处理剩余元素时，首先通过 max_wave = max(max_wave, nums[dq.front()]) 更新当前窗口的最大波谷的值，然后通过两个while循环，分别将队列中不在当前l-序列范围内的元素移除，并且保持队列中的元素按照递减的顺序排列。最后将当前元素的下标加入队列中。

  3. 最后处理最后一个l-序列的波谷，通过 max_wave = max(max_wave, nums[dq.front()]) 更新最终的最大波谷的值。

这个算法的关键是使用双端队列维护一个单调递减的队列，队列中的元素表示当前窗口的候选最小值，每次遍历新的元素时，都会更新队列，保持队列的单调性。这样就可以在O(1)时间内找到当前窗口的最小值。整个算法的时间复杂度为O(n)，其中n是原序列的长度。

方法三（优先队列/最小堆）：

这个方法大体和方法二相同，但是思路比方法二简单，少了一个维护队列有序的过程，因为优先队列/最小堆的top就是最小值。

  1. 首先处理前l个元素，建立一个最小堆。

  2. 然后从第l+1个元素开始滑动窗口，把堆顶不是属于这个l-序列的pop掉，连续pop直到队列为空或者堆顶在这个l-序列中(因为最小堆堆顶就是这个l-序列的最小值，我们只关心堆顶，如果现在堆下方还有不属于l-序列中的元素，直接不管)。

  3. push新的元素，优先队列自动维护堆顶最小值。更新max_wave

这个算法由于总是要维护一个最小堆，因此时间复杂度为O(l*logl) + O((n-l)logl) = O(nlogl)

完整代码

  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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 寻找原序列中特定长度的 l-序列的最大波谷
int findMaxWave(vector<int>& nums, int l) {
    int n = nums.size();
    int max_wave = -1; // 最大波谷

    for (int i = 0; i <= n - l; ++i) {
        int min_val = nums[i];
        for (int j = 1; j < l; ++j) {
            min_val = min(min_val, nums[i + j]); // 找到当前 l-序列的最小值
        }
        max_wave = max(max_wave, min_val); // 更新最大波谷
    }

    return max_wave;
}

int main() {
    // 示例输入
    int input_arr[] = {3, 1, 4, 2, 5, 1, 6, 4, 7, 8};
    vector<int> nums(input_arr, input_arr + sizeof(input_arr) / sizeof(input_arr[0]));
    
    int l = 4; // l-序列的长度
    
    // 寻找最大波谷
    int max_wave = findMaxWave(nums, l);
    
    // 输出结果
    cout << "原序列中长度为 " << l << " 的 l-序列的最大波谷为: " << max_wave << endl;
    
    return 0;
}

运行结果

1
原序列中长度为 4 的 l-序列的最大波谷为: 4
  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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <vector>
#include <deque>

using namespace std;

// 寻找原序列中特定长度的 l-序列的最大波谷
int findMaxWave(const vector<int>& nums, int l) {
    int n = nums.size();
    deque<int> dq; // 单调递减队列，存储元素下标
    int max_wave = -1; // 最大波谷

    // 处理前l个元素
    for (int i = 0; i < l; ++i) {
        // 将队列中比当前元素小的元素移除，保持单调递减性质
        while (!dq.empty() && nums[i] <= nums[dq.back()]) {
            dq.pop_back();
        }
        dq.push_back(i);
    }
    cout<<"dq为：";
	for(int i=0;i<dq.size();i++)
		cout<<dq[i]<<" ";
	cout<<endl;
    // 处理剩余元素
    for (int i = l; i < n; ++i) {
        // 波谷的值为队列中第一个元素的值
        max_wave = max(max_wave, nums[dq.front()]);
        
        // 移除队列中不在当前l-序列范围内的元素
        while (!dq.empty() && dq.front() <= i - l) {
            dq.pop_front();
        }
        
        // 将队列中比当前元素小的元素移除，保持单调递减性质
        while (!dq.empty() && nums[i] <= nums[dq.back()]) {
            dq.pop_back();
        }
        dq.push_back(i);
        cout<<"dq为：";
        for(int i=0;i<dq.size();i++)
			cout<<dq[i]<<" ";
		cout<<endl;
    }

    // 处理最后一个l-序列的波谷
    max_wave = max(max_wave, nums[dq.front()]);
    
    return max_wave;
}

int main() {
    // 示例输入
    int input_arr[] = {3, 1, 4, 2, 5, 1, 6, 4, 7, 8};
    vector<int> nums(input_arr, input_arr + sizeof(input_arr) / sizeof(input_arr[0]));
    int l = 4; // l-序列的长度
    
    // 寻找最大波谷
    int max_wave = findMaxWave(nums, l);
    
    // 输出结果
    cout << "原序列中长度为 " << l << " 的 l-序列的最大波谷为: " << max_wave << endl;
    
    return 0;
}

运行结果

1
2
3
4
5
6
7
8
dq为：1 3
dq为：1 3 4
dq为：5
dq为：5 6
dq为：5 7
dq为：5 7 8
dq为：7 8 9
原序列中长度为 4 的 l-序列的最大波谷为: 4

方法三：

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
#include<bits/stdc++.h>
using namespace std;

struct Element{
	int value;
	int index; 
	
	// 构造函数
    Element(int v, int i) : value(v), index(i) {}
    
    // 重载小于操作符
    bool operator<(const Element& other) const {
        // 如果值不同，则按值排序
        if (value != other.value) {
            return value > other.value; // 小于号表示最小堆
        }
        // 如果值相同，则按序号排序
        return index > other.index; // 小于号表示最小堆
    }
};

void printminHeap(priority_queue<Element> minHeap){
    // 克隆一份优先队列
    priority_queue<Element> clonedHeap = minHeap;

    // 打印克隆的优先队列中的所有元素
    cout << "minHeap priority queue:";
    while (!clonedHeap.empty()) {
        Element top = clonedHeap.top();
        cout <<  top.value << " ";
        clonedHeap.pop();
    }	
	cout<<endl;
}

int findMaxWave(const vector<int>& nums, int l){
	int n = nums.size();
	int max_wave = -1; // 最大波谷
	// 使用自定义类型创建最小堆
	priority_queue<Element> minHeap;
	
	for(int i=0;i<l;i++)
		minHeap.push(Element(nums[i],i));
		
	printminHeap(minHeap);//显示一下 
	
	for(int i=l;i<n;i++){
		
			
		// 移除队列中不在当前l-序列范围内的元素
		while(minHeap.top().index <= i -l  && !minHeap.empty())
			minHeap.pop();
		
		minHeap.push(Element(nums[i],i));
		
		printminHeap(minHeap);//显示一下 
		
		if(minHeap.top().value > max_wave)
			max_wave = minHeap.top().value;
	}
	
	return max_wave;
}
int main(){
	// 示例输入
    int input_arr[] = {3, 1, 4, 2, 5, 1, 6, 4, 7, 8};
    vector<int> nums(input_arr, input_arr + sizeof(input_arr) / sizeof(input_arr[0]));
    int l = 4; // l-序列的长度
    
    // 寻找最大波谷
    int max_wave = findMaxWave(nums, l);
    
    // 输出结果
    cout << "原序列中长度为 " << l << " 的 l-序列的最大波谷为: " << max_wave << endl;
    
	return 0;
}

运行结果

1
2
3
4
5
6
7
8
minHeap priority queue:1 2 3 4
minHeap priority queue:1 2 3 4 5
minHeap priority queue:1 2 3 4 5
minHeap priority queue:1 2 3 4 5 6
minHeap priority queue:1 2 3 4 4 5 6
minHeap priority queue:1 2 3 4 4 5 6 7
minHeap priority queue:4 5 6 7 8
原序列中长度为 4 的 l-序列的最大波谷为: 4