当前位置：首页 > news >正文

数据结构：单调栈

news 2026/6/6 7:46:43

单调的栈
如果为单调递增的栈，在栈内有元素时，判断栈顶元素和要加入的元素的大小，如果要加入的元素小于栈顶元素，就先让栈顶元素出栈，直到要加入元素比栈顶元素大为止；
解决什么问题？

当前元素左右侧，距离最近，并且比当前元素大的元素在哪里
当前元素左右侧，距离最近，并且比当前元素小的元素在哪里

int a = [1, 4, 10, 6, 3, 3, 15, 21, 8]

例如，要解决获得每个元素左侧的最近的比自己大的数字的下标，从最左侧开始遍历：

如果遍历到数a时，栈为空，则说明左侧没有比自己小的元素（或自己本身就是第一个元素），将结果数组填入零，并且自己的下标入栈；
如果遍历到数a时，栈中的栈顶元素b比a小，由于a必然会在结束后进栈，并且a大于b，所以此时栈中的b不可能成为后续所有数的答案，可以放心的把b从栈中出栈，然后判断下一个栈顶元素和a的大小；
如果栈顶元素大于a，则此时这个元素就是最靠近a的且大于a的数，将答案填入，并且将a入栈；
实现方式：

严格单调
栈中存储下标

寻找左侧比自己大的数：（顺序单调递减栈）

#include<iostream>
#include<stack>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int ret[N]; // 用来存放结果
int n;
void test()
{stack<int> st; //存放的是下标，为了直接便于往结果数组里面存for (int i = 1; i <= n; i++){while(st.size() && a[st.top()] <= a[i]) st.pop();  //严格单调递减栈if (st.size()) ret[i] = 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;
}

寻找左侧比自己小的数

void test()
{stack<int> st; //存放的是下标，为了直接便于往结果数组里面存for (int i = 1; i <= n; i++){while(st.size() && a[st.top()] >= a[i]) st.pop();  //严格单调递减栈if (st.size()) ret[i] = st.top();st.push(i);}for (int i = 1; i <= n; i++){cout << ret[i] << " ";}cout << endl;
}