单调栈模板代码(左小于右小于),无论是否有重复元素
1.
目的是求每一个元素的左小于右小于.
思路是单调栈.
维护数据的时候是每入栈的时候维护.
每一次入栈元素的时候,维护栈的单调性.
对于此时需要入栈的元素,栈顶元素一定是最近小于自己的元素下标.
然后入栈.
/*
单调栈的全新版本!!!
不管你有没有重复都是这样写!!!
*/
#if 1
using namespace std; // 使用标准命名空间
#include<bits/stdc++.h> // 包含所有标准库
#define int long long // 将 int 定义为 long long 类型
#define p pair<int,int> // 将 p 定义为 pair<int, int> 类型
#define MOD 1e9+7 // 定义常量 MOD 为 1e9 + 7
#define endl '\n' // 将 endl 定义为 '\n',用于换行
vector<p> d = { {0,1},{1,0},{-1,0},{0,-1} }; // 定义一个方向向量,用于表示四个方向
vector<int> arr; // 定义一个整型向量 arr
vector<p> p_min; // 定义一个存储 pair<int, int> 的向量 p_min
int n; // 定义一个整型变量 n
vector<int>st; // 定义一个整型向量 st
// 初始化函数
void init(){
arr = { 3,4,6,2,4,5,7,5,3,1,8 }; // 初始化 arr 向量
n = arr.size(); // 获取 arr 的大小
p_min.assign(n,{0,0}); // 初始化 p_min,大小为 n,所有元素为 {0,0}
}
// 解决函数
void solve(){
// 遍历每个元素,找到每个元素左边第一个比它小的元素
for (int i = 0; i < n; i++) {
while (1) {
if (st.empty())break; // 如果栈为空,跳出循环
if (arr[i] > arr[st.back()])break; // 如果当前元素大于栈顶元素,跳出循环
st.pop_back(); // 弹出栈顶元素
}
p_min[i].first = st.empty() ? -1 : st.back(); // 记录左边第一个比当前元素小的元素索引
st.push_back(i); // 将当前元素索引入栈
}
st.clear(); // 清空栈
// 遍历每个元素,找到每个元素右边第一个比它小的元素
for (int i = n - 1; i >= 0; i--) {
while (1) {
if (st.empty())break; // 如果栈为空,跳出循环
if (arr[i] > arr[st.back()])break; // 如果当前元素大于栈顶元素,跳出循环
st.pop_back(); // 弹出栈顶元素
}
p_min[i].second = st.empty() ? -1 : st.back(); // 记录右边第一个比当前元素小的元素索引
st.push_back(i); // 将当前元素索引入栈
}
// 输出 arr 向量中的所有元素
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
// 输出元素的索引
for (int i = 0; i < n; i++) {
cout << i << " ";
}
cout << endl;
// 输出每个元素左边和右边第一个比它小的元素的索引
for (int i = 0; i < n; i++) {
cout <<i<<":"<< p_min[i].first << " " << p_min[i].second << endl;
}
}
// 主函数
signed main() {
ios::sync_with_stdio(false); // 禁用同步,以提高 I/O 性能
cin.tie(nullptr); // 解除 cin 和 cout 的绑定
cout.tie(nullptr); // 解除 cout 的绑定
init(); // 调用初始化函数
solve(); // 调用解决函数
}
#endif // 1
单调栈结构(进阶)-牛客网(左最近小于,右最近小于)
描述
给定一个可能含有重复值的数组 arr,找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。
输入描述:
第一行输入一个数字 n,表示数组 arr 的长度。 以下一行输入 n 个数字,表示数组的值
输出描述:
输出n行,每行两个数字 L 和 R,如果不存在,则值为 -1,下标从 0 开始。
示例1
输入:
7 3 4 1 5 6 2 7
复制
输出:
-1 2 0 2 -1 -1 2 5 3 5 2 -1 5 -1
复制
备注:
1 \leq n \leq 10000001≤n≤1000000 -1000000 \leq arr_i \leq 1000000−1000000≤arri≤1000000
/*
单调栈的全新版本!!!
不管你有没有重复都是这样写!!!
*/
#if 1
using namespace std; // 使用标准命名空间
#include<bits/stdc++.h> // 包含所有标准库
#define int long long // 将 int 定义为 long long 类型
#define p pair<int,int> // 将 p 定义为 pair<int, int> 类型
#define MOD 1e9+7 // 定义常量 MOD 为 1e9 + 7
#define endl '\n' // 将 endl 定义为 '\n',用于换行
vector<p> d = { {0,1},{1,0},{-1,0},{0,-1} }; // 定义一个方向向量,用于表示四个方向
vector<int> arr; // 定义一个整型向量 arr
vector<p> p_min; // 定义一个存储 pair<int, int> 的向量 p_min
int n; // 定义一个整型变量 n
vector<int>st; // 定义一个整型向量 st
// 初始化函数
void init(){
cin>>n; // 从标准输入读取 n 的值
arr.assign(n,0); // 初始化 arr 向量,大小为 n,所有元素初始化为 0
for(int i=0;i<n;i++){
cin>>arr[i]; // 从标准输入读取 arr 的每个元素
}
p_min.assign(n,{0,0}); // 初始化 p_min,大小为 n,所有元素为 {0,0}
}
// 解决函数
void solve(){
// 遍历每个元素,找到每个元素左边第一个比它小的元素
for (int i = 0; i < n; i++) {
while (1) {
if (st.empty())break; // 如果栈为空,跳出循环
if (arr[i] > arr[st.back()])break; // 如果当前元素大于栈顶元素,跳出循环
st.pop_back(); // 弹出栈顶元素
}
p_min[i].first = st.empty() ? -1 : st.back(); // 记录左边第一个比当前元素小的元素索引
st.push_back(i); // 将当前元素索引入栈
}
st.clear(); // 清空栈
// 遍历每个元素,找到每个元素右边第一个比它小的元素
for (int i = n - 1; i >= 0; i--) {
while (1) {
if (st.empty())break; // 如果栈为空,跳出循环
if (arr[i] > arr[st.back()])break; // 如果当前元素大于栈顶元素,跳出循环
st.pop_back(); // 弹出栈顶元素
}
p_min[i].second = st.empty() ? -1 : st.back(); // 记录右边第一个比当前元素小的元素索引
st.push_back(i); // 将当前元素索引入栈
}
// 输出每个元素左边和右边第一个比它小的元素的索引
for(int i=0;i<n;i++){
cout<<p_min[i].first<<" "<<p_min[i].second<<endl; // 输出结果
}
}
// 主函数
signed main() {
ios::sync_with_stdio(false); // 禁用同步,以提高 I/O 性能
cin.tie(nullptr); // 解除 cin 和 cout 的绑定
cout.tie(nullptr); // 解除 cout 的绑定
init(); // 调用初始化函数
solve(); // 调用解决函数
}
#endif // 1
结尾
最后,感谢您阅读我的文章,希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点,请随时在评论区留言。
同时,不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中,我将继续探讨这个话题的不同方面,为您呈现更多深度和见解。
谢谢您的支持,期待与您在下一篇文章中再次相遇!