你好用c++给我写个单调栈
时间: 2023-07-04 12:11:52 浏览: 63
当然可以,以下是一个简单的单调栈的 C++ 实现:
```c++
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
vector<int> next_greater_element(const vector<int>& nums) {
int n = nums.size();
vector<int> result(n, -1); // 初始化结果为 -1
stack<int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && nums[i] > nums[st.top()]) {
result[st.top()] = i; // 当前元素是栈顶元素的下一个更大元素
st.pop();
}
st.push(i);
}
return result;
}
int main() {
vector<int> nums = {1, 3, 2, 4, 5, 6};
vector<int> result = next_greater_element(nums);
for (int i = 0; i < nums.size(); i++) {
cout << nums[i] << ": ";
if (result[i] == -1) {
cout << "no next greater element" << endl;
} else {
cout << nums[result[i]] << endl;
}
}
return 0;
}
```
这个程序实现了一个函数 `next_greater_element`,给定一个整数数组 `nums`,返回一个新的数组,其中第 `i` 个元素为 `nums[i]` 的下一个更大的元素的下标,如果不存在下一个更大的元素,则为 -1。
单调栈的主要思想是维护一个单调递减的栈(或单调递增的栈),每当新元素入栈时,将栈中所有小于它的元素都弹出栈,因为它们已经找到了自己的下一个更大元素,而当前元素就是它们的下一个更大元素。在上面的代码中,我们使用一个栈来存储数组元素的下标,以便在需要时可以方便地访问元素值和下标。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)