算法基础-（数据结构）

1.单调栈

1.什么是单调栈？

#include <iostream> #include <stack> using namespace std; const int N = 3e6 + 10; int a[N], n; // 单调递增栈 void test1() { stack<int> st; for (int i = 1; i <= n; i++) { while (st.size() && st.top() >= a[i]) st.pop(); st.push(a[i]); } // 输出栈内元素（递增） cout << "单调递增栈结果："; while (!st.empty()) { cout << st.top() << " "; st.pop(); } cout << endl; } // 单调递减栈 void test2() { stack<int> st; for (int i = 1; i <= n; i++) { while (st.size() && st.top() <= a[i]) st.pop(); st.push(a[i]); } // 输出栈内元素（递减） cout << "单调递减栈结果："; while (!st.empty()) { cout << st.top() << " "; st.pop(); } cout << endl; } int main() { // 测试用例：n=5，数组a=[3,1,4,2,5] n = 5; a[1] = 3; a[2] = 1; a[3] = 4; a[4] = 2; a[5] = 5; test1(); // 递增栈结果：1 2 5 test2(); // 递减栈结果：5 4 3 return 0; }

2.单调栈解决的问题

3.寻找当前元素左侧，离它最近，并且⽐它⼤的元素在哪

#include <iostream> #include <stack> using namespace std; const int N = 3e6 + 10; int a[N], n; int ret[N]; void test() { stack<int> st; // 单调递增栈：存储下标 for (int i = 1; i <= n; i++) ret[i] = 0; // 逆序遍历：找右侧第一个更小的元素 for (int i = n; i >= 1; i--) { // 弹出栈中≥当前值的下标 while (st.size() && a[st.top()] >= a[i]) { st.pop(); } // 栈非空：右侧第一个更小元素的值 if (st.size()) { ret[i] = a[st.top()]; } st.push(i); } for (int i = 1; i <= n; i++) { cout << ret[i] << " "; } cout << endl; } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } test(); return 0; }

4.寻找当前元素左侧，离它最近，并且⽐它⼩的元素在哪

#include <iostream> // 输入输出头文件：用来输入数字、输出结果 #include <stack> // 栈的头文件：用来使用“栈”这个工具 using namespace std; // 定义数组最大长度，3e6+10表示足够装下大量数字（不用改） const int N = 3e6 + 10; int a[N], n; // a[N]：装输入的数字；n：装数字的总个数 int ret[N]; // ret[N]：装最终结果（每个数左边最近更小的数的下标） void test() { // 定义一个栈，栈里存的是数字的“下标”（抽屉编号），维护单调递增的栈 stack<int> st; // 从第1个数字到第n个数字，逐个处理 for(int i = 1; i <= n; i++) { // 核心逻辑：把栈里≥当前数字的下标都弹出（保证栈是递增的） // st.size()：判断栈里有没有东西；a[st.top()]：栈顶下标对应的数字 while(st.size() && a[st.top()] >= a[i]) { st.pop(); // 弹出栈顶（扔掉不符合的下标） } // 如果栈里还有东西，栈顶就是“左边最近更小的数的下标” if(st.size()) { ret[i] = st.top(); } else { ret[i] = 0; // 栈空=没找到，填0 } // 把当前数字的下标放进栈里，维护栈的递增性 st.push(i); } // 输出结果：从第1个到第n个，逐个打印ret里的数 for(int i = 1; i <= n; i++) { cout << ret[i] << " "; } cout << endl; } int main() { // 第一步：输入数字的总个数（测试用例里是9） cin >> n; // 第二步：输入n个数字，依次放进a[1]到a[n]（抽屉1到抽屉n） for(int i = 1; i <= n; i++) { cin >> a[i]; } // 第三步：执行找“左边最近更小数下标”的逻辑 test(); return 0; }

5.寻找当前元素右侧，离它最近，并且⽐它⼤的元素在哪

#include <iostream> // 输入输出工具：能输入数字、输出结果 #include <stack> // 栈工具：用来找“右侧最近更大的数” using namespace std; const int N = 3e6 + 10; // 准备足够多的“抽屉”（不用改，够装数字就行） int a[N], n; // a抽屉：装输入的9个数字；n：记数字的总个数（比如9） int ret[N]; // ret抽屉：装最终结果（每个数的答案） void test() { stack<int> st; // 拿出空的“栈盒子”（维护单调递减，只存下标） // 核心：从最后一个数往第一个数遍历（右→左） for(int i = n; i >= 1; i--) { // 第一步：把栈里≤当前数的下标都扔掉（保证栈是递减的） // st.size()：盒子里有东西吗？a[st.top()]：栈顶下标对应的数字 while(st.size() && a[st.top()] <= a[i]) { st.pop(); // 扔掉不符合的下标 } // 第二步：填结果 if(st.size()) { ret[i] = st.top(); // 栈非空→栈顶是“右侧最近更大数的下标” } else { ret[i] = 0; // 栈空→没找到，填0 } // 第三步：把当前数的下标放进栈里 st.push(i); } // 输出结果：从第1个到第9个，逐个打印ret抽屉里的数 for(int i = 1; i <= n; i++) { cout << ret[i] << " "; } cout << endl; } int main() { cin >> n; // 输入9（告诉程序有9个数） // 把1、4、10、6、3、3、15、21、8依次放进a[1]~a[9] for(int i = 1; i <= n; i++) { cin >> a[i]; } test(); // 执行找“右侧最近更大数下标”的逻辑 return 0; }

6.寻找当前元素右侧，离它最近，并且⽐它⼩的元素在哪

#include <iostream> // 输入输出工具：输入数字、输出结果 #include <stack> // 栈工具：找右侧最近更小的数 using namespace std; const int N = 3e6 + 10; // 足够多的“抽屉”，装数字和结果 int a[N], n; // a：装输入的数字；n：数字总个数 int ret[N]; // ret：装最终结果（每个数的答案） void test() { stack<int> st; // 空栈，维护单调递增（只存下标） // 从最后一个数往第一个数遍历（右→左） for(int i = n; i >= 1; i--) { // 核心：弹出栈里≥当前数的下标（保证栈递增） // st.size()：栈里有东西吗？a[st.top()]：栈顶下标对应的数字 while(st.size() && a[st.top()] >= a[i]) { st.pop(); // 扔掉不符合的下标 } // 填结果：栈非空=找到答案，栈空=填0 if(st.size()) { ret[i] = st.top(); } else { ret[i] = 0; // 补充初始化，避免随机值 } // 把当前数的下标放进栈，维护递增性 st.push(i); } // 输出结果：从第一个数到最后一个数打印 for(int i = 1; i <= n; i++) { cout << ret[i] << " "; } cout << endl; } int main() { cin >> n; // 输入数字个数（比如9） // 把数字依次放进a[1]~a[n] for(int i = 1; i <= n; i++) { cin >> a[i]; } test(); // 执行找数逻辑 return 0; }

💡总结：

1.1【模板】单调栈

题目背景

模板题，无背景。

2019.12.12 更新数据，放宽时限，现在不再卡常了。

题目描述

给出项数为 n 的整数数列 a1…n​。

定义函数 f(i) 代表数列中第 i 个元素之后第一个大于 ai​ 的元素的下标，即 f(i)=mini<j≤n,aj​>ai​​{j}。若不存在，则 f(i)=0。

试求出 f(1…n)。

输入格式

第一行一个正整数 n。

第二行 n 个正整数 a1…n​。

输出格式

一行 n 个整数表示 f(1),f(2),…,f(n) 的值。

输入输出样例

输入 #1复制

5 1 4 2 3 5

输出 #1复制

2 5 4 5 0

说明/提示

【数据规模与约定】

对于 30% 的数据，n≤100；

对于 60% 的数据，n≤5×103 ；

对于 100% 的数据，1≤n≤3×106，1≤ai​≤109。

【解法】

【参考代码】

#include <iostream> // 输入输出工具：输入数字、输出结果 #include <stack> // 栈工具：找右侧第一个更大的数 using namespace std; const int N = 3e6 + 10; // 足够多的“抽屉”，装数字和结果（适配3e6的大数据） int n; // 数列的长度（比如示例里的5） int a[N]; // a抽屉：装输入的数列（a[1]=1, a[2]=4...） int ret[N]; // ret抽屉：装每个数的答案（右边第一个更大数的下标，没找到填0） int main() { // 第一步：输入数列长度和数列本身 cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i]; // 把数字依次放进a[1]到a[n] } stack<int> st; // 空栈：维护单调递减，只存“下标”（抽屉号） // 第二步：逆序遍历（从最后一个数到第一个数） for(int i = n; i >= 1; i--) { // 核心：弹出栈里≤当前数的下标（保证栈是递减的） // st.size()：栈里有东西吗？a[st.top()]：栈顶下标对应的数字 while(st.size() && a[st.top()] <= a[i]) { st.pop(); // 扔掉不符合的下标 } // 第三步：填答案 if(st.size()) { ret[i] = st.top(); // 栈非空→栈顶是“右边第一个更大数的下标” } else { ret[i] = 0; // 栈空→没找到，填0 } // 第四步：把当前数的下标放进栈，维护递减性 st.push(i); } // 第五步：输出结果（如果要输出“值”，把ret[i]改成a[ret[i]]即可） for(int i = 1; i <= n; i++) { // 示例输出是下标，所以输出ret[i]；若要输出值，改成cout << a[ret[i]] << " "; cout << ret[i] << " "; } cout << endl; return 0; }

1.2发射站

题目描述

某地有 N 个能量发射站排成一行，每个发射站 i 都有不相同的高度 Hi​，并能向两边（两端的发射站只能向一边）同时发射能量值为 Vi​ 的能量，发出的能量只被两边最近的且比它高的发射站接收。显然，每个发射站发来的能量有可能被 0 或 1 或 2 个其他发射站所接受。

请计算出接收最多能量的发射站接收的能量是多少。

输入格式

第 1 行一个整数 N。

第 2 到 N+1 行，第 i+1 行有两个整数 Hi​ 和 Vi​，表示第 i 个发射站的高度和发射的能量值。

输出格式

输出仅一行，表示接收最多能量的发射站接收到的能量值。答案不超过 32 位带符号整数的表示范围。

输入输出样例

输入 #1复制

3 4 2 3 5 6 10

输出 #1复制

7

说明/提示

对于 40% 的数据，1≤N≤5000,1≤Hi​≤105,1≤Vi​≤104。

对于 70% 的数据，1≤N≤105,1≤Hi​≤2×109,1≤Vi​≤104。

对于 100% 的数据，1≤N≤106,1≤Hi​≤2×109,1≤Vi​≤104。

【解法】

#include <iostream> // 输入输出工具：输入发射站信息、输出结果 #include <stack> // 栈工具：找“最近更高的站” using namespace std; typedef long long LL; // 防止能量值太大溢出（比如多个能量相加超过int范围） const int N = 1e6 + 10; // 足够多的“抽屉”，装1e6个发射站的信息 int n; // 发射站的总数（比如示例里的3） LL h[N], v[N]; // h：装每个站的高度；v：装每个站的能量值 LL sum[N]; // sum：装每个站接收的总能量（初始都是0） int main() { // 第一步：输入发射站数量和每个站的高度、能量 cin >> n; for(int i = 1; i <= n; i++) { cin >> h[i] >> v[i]; // 站1的h=4、v=2；站2的h=3、v=5；站3的h=6、v=10 } // 第二步：找每个站“左边最近更高的站”，并把能量加给这个站 stack<int> st; // 空栈：维护单调递减（只存站的下标） for(int i = 1; i <= n; i++) { // 从左到右遍历每个站 // 核心：弹出栈里≤当前站高度的下标（保证栈是递减的） while(st.size() && h[st.top()] <= h[i]) { st.pop(); } // 栈非空：栈顶就是“左边最近更高的站”，接收当前站的能量 if(st.size()) { sum[st.top()] += v[i]; // 比如站2的左边更高是站1，sum[1] +=5 } // 把当前站的下标放进栈，维护递减性 st.push(i); } // 第三步：找每个站“右边最近更高的站”，并把能量加给这个站 while(st.size()) st.pop(); // 清空之前的栈 for(int i = n; i >= 1; i--) { // 从右到左遍历每个站 // 核心：弹出栈里≤当前站高度的下标（保证栈是递减的） while(st.size() && h[st.top()] <= h[i]) { st.pop(); } // 栈非空：栈顶就是“右边最近更高的站”，接收当前站的能量 if(st.size()) { sum[st.top()] += v[i]; // 比如站1的右边更高是站3，sum[3] +=2 } // 把当前站的下标放进栈，维护递减性 st.push(i); } // 第四步：找接收能量最多的站 LL ret = 0; // 存最大能量值（初始0） for(int i = 1; i <= n; i++) { ret = max(ret, sum[i]); // 逐个比较，保留最大的 } cout << ret << endl; // 输出7（示例） return 0; }