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

【算法模板】数据结构：单调栈

news 来源：原创 2024/9/19 23:56:32

算法思想

单调栈的核心思想是通过维护一个栈，使得栈内元素保持某种单调性（递增或递减），从而在遍历数组时可以快速确定当前元素相关的特定信息，如下一个更大元素、前一个更小元素等。具体的单调性取决于问题需求：

单调递增栈：栈内元素从栈底到栈顶保持递增顺序（即栈顶元素最小）。这种栈适合用于寻找某个元素的下一个更大元素或上一个更小元素。
单调递减栈：栈内元素从栈底到栈顶保持递减顺序（即栈顶元素最大）。这种栈适合用于寻找某个元素的下一个更小元素或上一个更大元素。

算法流程

以寻找下一个更大元素为例，算法流程如下：

初始化：创建一个空栈 stack，以及一个与输入数组 nums 等长的结果数组 result，初始值全部设置为 -1（表示没有找到更大元素）。
遍历数组：
- 对于数组中的每一个元素 nums[i]：
  1. 当栈不为空且 nums[i] 大于栈顶元素所对应的数组元素时，弹出栈顶元素，并将 result 数组中对应的位置更新为 nums[i]（因为此时 nums[i] 是栈顶元素的下一个更大元素）。
  2. 将当前元素的索引 i 压入栈中。
处理完成：
- 遍历结束后，栈中剩余的元素表示这些位置上没有比它们更大的元素，结果数组中对应的位置仍然保持为 -1。

算法模板

vector<int> findNextGreaterElement(const vector<int>& nums) {  int n = nums.size();  vector<int> ans(n, -1); // 初始化结果数组，所有位置都设为-1  stack<int> sta; // 用于存储元素的索引  for (int i = 0; i < n; i++) {  // 当栈不为空且当前元素大于栈顶索引对应的元素时  while (!sta.empty() && nums[sta.top()] < nums[i]) {  ans[sta.top()] = i; // 更新栈顶索引对应的结果  sta.pop(); // 弹出栈顶索引  }  sta.push(i); // 将当前索引压入栈  }  return ans; // 返回结果数组  
}

例题

P5788 【模板】单调栈

给定一个包含n个整数的数列a1,a2,…,an。

定义一个函数f(i)，该函数表示在数列中第i个元素之后（不包括第i个元素本身），第一个大于ai的元素的位置索引。如果不存在这样的元素，则f(i)=0。任务是计算并输出f(1),f(2),…,f(n)的值。

#include <bits/stdc++.h>
using namespace std;int main(){int n;cin>>n;vector<int> v(n);for(int &i:v)cin>>i;stack<int> sta;vector<int> ans(n,-1);for(int i=0;i<n;i++){while(not empty(sta) and v[sta.top()]<v[i]){ans[sta.top()]=i;sta.pop();}sta.push(i);}for(int i:ans)cout<<i+1<<' ';
}

P1901 发射站

某地有 N 个能量发射站排成一行，每个发射站 i 都有不相同的高度 Hi，并能向两边（两端的发射站只能向一边）同时发射能量值为 Vi 的能量，发出的能量只被两边最近的且比它高的发射站接收。显然，每个发射站发来的能量有可能被 0 或 1 或 2 个其他发射站所接受。

请计算出接收最多能量的发射站接收的能量是多少。

#include<bits/stdc++.h>
using namespace std;int main(){int n;cin>>n;vector<int> H(n);vector<int> val(n);for(int i=0;i<n;i++)cin>>H[i]>>val[i];vector nextG=[](vector<int> v){int n=v.size();vector<int> res(n,-1);stack<int> sta;for(int i=0;i<n;i++){while(not empty(sta) and v[sta.top()]<v[i]){res[sta.top()]=i;sta.pop();}sta.push(i);}return res;}(H);vector prevG=[](vector<int> v){int n=v.size();vector<int> res(n,-1);stack<int> sta;for(int i=n-1;~i;i--){while(not empty(sta) and v[sta.top()]<v[i]){res[sta.top()]=i;sta.pop();}sta.push(i);}return res;}(H);vector<int> ans(n);for(int i=0;i<n;i++){if(~nextG[i])ans[nextG[i]]+=val[i];if(~prevG[i])ans[prevG[i]]+=val[i];}cout<<*max_element(ans.begin(),ans.end())<<endl;
}