P5788 【模板】单调栈
时间: 2023-08-06 22:02:09 浏览: 63
单调栈是一种常用的数据结构,用于解决一些与单调性相关的问题。它可以在 O(n) 的时间复杂度内解决这些问题。
单调栈的基本思想是维护一个单调递增或单调递减的栈。在处理每个元素时,我们将栈中比当前元素小(或大)的元素弹出栈,然后将当前元素入栈。这样可以确保栈中的元素始终保持单调性。
关于单调栈的应用场景,其中一个常见的问题是找到数组中每个元素的下一个更大元素(Next Greater Element)。给定一个数组,对于每个元素,需要找到它右边第一个比它大的元素。使用单调栈可以在线性时间内解决这个问题。
下面是一个使用单调栈解决 Next Greater Element 问题的示例代码:
```cpp
vector<int> nextGreaterElement(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[st.top()] < nums[i]) {
result[st.top()] = nums[i]; // 当前元素是栈顶元素右边第一个更大的元素
st.pop();
}
st.push(i);
}
return result;
}
```
以上代码中,我们使用一个栈来存储数组的索引。遍历数组,对于每个元素,如果栈不为空且栈顶元素小于当前元素,说明栈顶元素的下一个更大元素就是当前元素。将栈顶元素出栈,并更新结果数组中对应位置的值为当前元素。最后将当前元素的索引入栈。遍历完成后,返回结果数组即可。
除了 Next Greater Element 问题,单调栈还可以用于解决其他一些与单调性相关的问题,如 Next Smaller Element、Largest Rectangle in Histogram 等。希望这个模板能对你有所帮助!有其他问题欢迎继续提问。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![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)