单调栈,顾名思义,栈中的内容是单调的,我们可以利用这里特性解决一些有趣的问题,如:
水池问题: 给定一组高度,如[0,1,0,2,1,0,1,3,2,1,2,1]
,返回可以装的水量6
最大面积问题:给定一组高度如[2,1,5,6,2,3]
,返回最大矩形面积10
题目中要求所有值左边👈和右边👉最近的较小值,可以利用单调递增栈:
- 如果当前元素大于栈顶元素,将元素下标入栈
- 如果当前元素小于栈顶元素,一一出栈,直到栈顶下标对应元素大于当前元素,然后将当前元素的下标入栈
- 出栈的过程中,第一个栈顶即为当前元素左边的较小值,剩下的栈顶对应元素的右边较小值为当前元素
遍历完整个数组后,如果栈不为空,一一出栈,此时下标对应的元素无右边较小值,左边较小值为下一个栈顶对应的数组元素。
代码如下:
// // Created by jt on 2020/8/27. // #include <iostream> #include <vector> #include <stack> using namespace std; int main() { int n; cin >> n; vector<int> vec; for (int i = 0; i < n; ++i) { int a; cin >> a; vec.push_back(a); } stack<int> st; // 单调递增栈 vector<int> left(n, -1), right(n, -1); // 分别存储左边较小值和右边较小值的下标 for (int i = 0; i < n; ++i) { while(!st.empty() && vec[i] < vec[st.top()]) { int cur = st.top(); st.pop(); if (!st.empty()) left[cur] = st.top(); right[cur] = i; } st.push(i); // 将当前元素的下标入栈 } while(!st.empty()) { int cur = st.top(); st.pop(); if (!st.empty()) left[cur] = st.top(); } for (int i = 0; i < n; ++i) { cout << left[i] << ' ' << right[i] << endl; } }