acwing算法基础之数据结构--栈和队列

1 知识点

栈：先进后出。先进的就是栈底，后进的就是栈顶。后进先出嘛，所以在栈顶弹出元素。

队列：先进先出。先进的就是队头，后进的就是队尾。先进先出嘛，所以在队头弹出元素。

单调栈：输入数组，求每个元素左边的某个元素，满足（1）比它小，（2）离它最近。

//输入数组nums
//输出上述要求的数值
for (int i = 0; i < nums.size(); ++i) {
	while (tt && stk[tt] >= nums[i]) {
		tt--;
	}
	if (tt) {
		cout << stk[tt] << " ";
	} else {
		cout << "-1 ";
	}
	stk[++tt] = nums[i];
}
cout << endl;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

单调队列：求滑动窗口中的最大值或最小值，

//输入数组nums，区间长度k
//（1）找到滑动窗口的最小值
int hh = 0, tt = -1;
for (int i = 0; i < nums.size(); ++i) {
	if (hh <= tt && q[hh] < i - k + 1) {
		hh++;
	}
	while (hh <= tt && nums[q[tt]] >= nums[i]) {
		tt--;
	}
	q[++tt] = i;
	//最小值nums[q[hh]]
	if (i >= k-1) {
		cout << nums[q[hh]] << " ";
	}
}
cout << endl;

//滑动区间的最大值
int hh = 0, tt = -1;
for (int i = 0; i < nums.size(); ++i) {
	if (hh <= tt && q[hh] < i - k + 1) {
		hh++;
	}
	while (hh <= tt && nums[q[tt]] <= nums[i]) {
		tt--;
	}
	q[++tt] = i;
	//最大值nums[q[hh]]
	if (i >= k - 1) {
		cout << nums[q[hh]] << " ";
	}
}
cout << endl;
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

用数组来模拟上述数据结构。

2 模板

（一）用数组来模拟栈的模板，

const int N = 1e6 + 10;
int stk[N], tt = 0;//tt表示栈顶下标，stk[tt]表示栈顶的值。

//（1）往栈中插入数值x
stk[++tt] = x;

//（2）删除栈顶元素
tt--;

//（3）栈顶元素的值
stk[tt];

//（4）判断栈是否为空
if (tt > 0) {
	//栈不为空
} else {
	//栈为空
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

（二）用数组来模拟队列的模板，

const int N = 1e6 + 10;
int q[N], hh = 0, tt = -1;//hh表示队头下标，tt表示队尾下标。q[hh]表示队头的值，q[tt]表示队尾的值。

//（1）往队列中插入数值x
q[++tt] = x;

//（2）往队列中删除元素
hh++;

//（3）取队头元素
q[hh];

//（4）取队尾元素
q[tt];

//（5）判断队列是否为空
if (hh <= tt) {
	//队列不为空
} else {
	//队列为空
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3 单调栈题目

题目1：给定$n$和$x_0,x_1,x_2,\cdots ,x_{n-1}$，求每个$x_i$左边最近的且小于它的数，如果这个数不存在，则输出-1。

解题思路：单调栈。

C++代码如下，

#include 
#include 

using namespace std;

const int N = 1e5 + 10;
int n;

int main() {
    cin >> n;
    
    //找到arr[i]左边最近的且小于它的元素
    vector<int> stk;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        
        while (!stk.empty() && stk.back() >= x) {
            stk.pop_back();
        }
        
        if (stk.empty()) {
            cout << "-1 "; 
        } else {
            cout << stk.back() << " ";
        }
        
        stk.emplace_back(x);
    }
    return 0;
}
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

测试用例，

输入：
5
3 4 2 7 5
输出：
-1 3 -1 2 2
1
2
3
4
5

题目2：给定$n$和$x_0,x_1,x_2,\cdots ,x_{n-1}$，求每个$x_i$左边最近的且小于等于它的数，如果这个数不存在，则输出-1。

同样使用单调栈来求解。

C++代码如下，

#include 
#include 

using namespace std;

const int N = 1e5 + 10;
int n;

int main() {
    cin >> n;
    
    //找到arr[i]左边最近的且小于等于它的元素
    vector<int> stk;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        
        while (!stk.empty() && stk.back() > x) {
            stk.pop_back();
        }
        
        if (stk.empty()) {
            cout << "-1 "; 
        } else {
            cout << stk.back() << " ";
        }
        
        stk.emplace_back(x);
    }
    return 0;
}
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

测试用例，

输入：
6
3 4 2 5 7 5
输出：
-1 3 -1 2 5 5 
1
2
3
4
5

题目3：给定$n$和$x_0,x_1,x_2,\cdots ,x_{n-1}$，求每个$x_i$右边最近的且小于它的数，如果这个数不存在，则输出-1。

同样使用单调栈来求解，只不过遍历顺序需要从$n-1$到$0$。

C++代码如下，

#include 
#include 

using namespace std;

const int N = 1e5 + 10;
int x[N];
int n;

int main() {
    cin >> n;
    
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    
    //找到arr[i]右边最近的且小于它的元素
    vector<int> right(n);
    vector<int> stk;    
    for (int i = n - 1; i >= 0; --i) {
        while (!stk.empty() && stk.back() >= x[i]) {
            stk.pop_back();
        }
        if (stk.empty()) {
            right[i] = -1;
        } else {
            right[i] = stk.back();
        }
        stk.emplace_back(x[i]);
    }
    
    for (int i = 0; i < n; ++i) cout << right[i] << " ";
    cout << endl;
    
    return 0;
}
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

测试用例，

输入：
6
3 4 2 5 7 5
输出：
2 2 -1 -1 5 -1 
1
2
3
4
5

题目4：给定$n$和$x_0,x_1,x_2,\cdots ,x_{n-1}$，求每个$x_i$右边最近的且小于等于它的数，如果这个数不存在，则输出-1。

同样使用单调栈来求解。

C++代码如下，

#include 
#include 

using namespace std;

const int N = 1e5 + 10;
int x[N];
int n;

int main() {
    cin >> n;
    
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    
    //找到arr[i]右边最近的且小于等于它的元素
    vector<int> right(n);
    vector<int> stk;    
    for (int i = n - 1; i >= 0; --i) {
        while (!stk.empty() && stk.back() > x[i]) {
            stk.pop_back();
        }
        if (stk.empty()) {
            right[i] = -1;
        } else {
            right[i] = stk.back();
        }
        stk.emplace_back(x[i]);
    }
    
    for (int i = 0; i < n; ++i) cout << right[i] << " ";
    cout << endl;
    
    return 0;
}
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

测试用例，

输入：
6
3 4 2 5 7 5
输出：
2 2 -1 5 5 -1 
1
2
3
4
5

题目5：给定$n$和$x_0,x_1,x_2,\cdots ,x_{n-1}$，求每个$x_i$左边最近的且大于它的数，如果这个数不存在，则输出-1。

同样使用单调栈来求解。

#include 
#include 

using namespace std;

const int N = 1e5 + 10;
int n;
int a[N];
int res[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    //找到左边最近的且大于它的数，没有找到则输出-1。
    vector<int> stk;
    for (int i = 1; i <= n; ++i) {
        while (!stk.empty() && stk.back() <= a[i]) {
            stk.pop_back();
        }
        res[i] = stk.empty() ? -1 : stk.back();
        stk.emplace_back(a[i]);
    }
    
    //输出答案
    for (int i = 1; i <= n; ++i) {
        cout << res[i] << " ";
    }
    cout << endl;
    
    return 0;
}
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

测试用例，

输入：
6
3 4 2 2 7 5
输出：
-1 -1 4 4 -1 7 
1
2
3
4
5

题目6：给定$n$和$x_0,x_1,x_2,\cdots ,x_{n-1}$，求每个$x_i$左边最近的且大于等于它的数，如果这个数不存在，则输出-1。

C++代码如下，

#include 
#include 

using namespace std;

const int N = 1e5 + 10;
int n;
int a[N];
int res[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    //找到左边最近的且大于等于它的数，没有找到则输出-1。
    vector<int> stk;
    for (int i = 1; i <= n; ++i) {
        while (!stk.empty() && stk.back() < a[i]) {
            stk.pop_back();
        }
        res[i] = stk.empty() ? -1 : stk.back();
        stk.emplace_back(a[i]);
    }
    
    //输出答案
    for (int i = 1; i <= n; ++i) {
        cout << res[i] << " ";
    }
    cout << endl;
    
    return 0;
}
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

测试用例，

输入：
6
3 4 2 2 7 5
输出：
-1 -1 4 2 -1 7 
1
2
3
4
5

题目7：给定$n$和$x_0,x_1,x_2,\cdots ,x_{n-1}$，求每个$x_i$右边最近的且大于它的数，如果这个数不存在，则输出-1。

C++代码如下，

#include 
#include 

using namespace std;

const int N = 1e5 + 10;
int n;
int a[N];
int res[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    //找到右边最近的且大于它的数，没有找到则输出-1。
    vector<int> stk;
    for (int i = n; i >= 0; --i) {
        while (!stk.empty() && stk.back() <= a[i]) {
            stk.pop_back();
        }
        res[i] = stk.empty() ? -1 : stk.back();
        stk.emplace_back(a[i]);
    }
    
    //输出答案
    for (int i = 1; i <= n; ++i) {
        cout << res[i] << " ";
    }
    cout << endl;
    
    return 0;
}
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

测试用例，

输入：
6
3 4 2 2 7 5
输出：
4 7 7 7 -1 -1 
1
2
3
4
5

题目8：给定$n$和$x_0,x_1,x_2,\cdots ,x_{n-1}$，求每个$x_i$右边最近的且大于等于它的数，如果这个数不存在，则输出-1。

C++代码如下，

#include 
#include 

using namespace std;

const int N = 1e5 + 10;
int n;
int a[N];
int res[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    //找到右边最近的且大于它的数，没有找到则输出-1。
    vector<int> stk;
    for (int i = n; i >= 0; --i) {
        while (!stk.empty() && stk.back() < a[i]) {
            stk.pop_back();
        }
        res[i] = stk.empty() ? -1 : stk.back();
        stk.emplace_back(a[i]);
    }
    
    //输出答案
    for (int i = 1; i <= n; ++i) {
        cout << res[i] << " ";
    }
    cout << endl;
    
    return 0;
}
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

测试用例，

输入：
6
3 4 2 2 7 5
输出：
4 7 2 7 -1 -1 
1
2
3
4
5

4 单调队列题目

题目1：求滑动窗口内的最大值和最小值。

C++代码如下，

#include 
#include 
#include 

using namespace std;

const int N = 1e6 + 10;
int q[N], hh = 0, tt = -1;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> nums(n, 0);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    
    deque<int> q;
    for (int i = 0; i < n; ++i) {
        if (!q.empty() && q.front() < i - k + 1) {//如果队头元素不在滑动区间内部，则弹出
            q.pop_front();
        } 
        while (!q.empty() && nums[q.back()] >= nums[i]) {//需要的是滑动区间内的最小值，因此，如果队尾元素大于等于当前元素，则弹出队尾元素
            q.pop_back();
        }
        q.push_back(i);//往队尾插入
        if (i >= k - 1) {
            cout << nums[q.front()] << " ";//输出队头元素
        }
    }
    cout << endl;
    
    q.clear();
    for (int i = 0; i < n; ++i) {
        if (!q.empty() && q.front() < i - k + 1) {
            q.pop_front();
        } 
        while (!q.empty() && nums[q.back()] <= nums[i]) {
            q.pop_back();
        }
        q.push_back(i);
        if (i >= k - 1) {
            cout << nums[q.front()] << " ";
        }
    }
    cout << endl;    
    
    return 0;
}
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