【算法模板】数据布局：单调栈

算法头脑

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

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

算法流程

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

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

算法模板

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

复制代码

例题

P5788 【模板】单调栈
给定一个包罗n个整数的数列a1,a2,…,an。
界说一个函数f(i)，该函数体现在数列中第i个元素之后（不包罗第i个元素本身），第一个大于ai的元素的位置索引。假如不存在如许的元素，则f(i)=0。任务是盘算并输出f(1),f(2),…,f(n)的值。

1. #include <bits/stdc++.h>
2. using namespace std;
4. int main(){
5.     int n;
6.     cin>>n;
7.     vector<int> v(n);
8.     for(int &i:v)cin>>i;
9.     stack<int> sta;
10.     vector<int> ans(n,-1);
11.     for(int i=0;i<n;i++){
12.         while(not empty(sta) and v[sta.top()]<v[i]){
13.             ans[sta.top()]=i;
14.             sta.pop();
15.         }
16.         sta.push(i);
17.     }
18.     for(int i:ans)cout<<i+1<<' ';
19. }

复制代码

P1901 发射站
某地有 N 个能量发射站排成一行，每个发射站 i 都有不类似的高度 Hi，并能向双方（两端的发射站只能向一边）同时发射能量值为 Vi 的能量，发出的能量只被双方迩来的且比它高的发射站汲取。显然，每个发射站发来的能量有大概被 0 或 1 或 2 个其他发射站所担当。
请盘算出汲取最多能量的发射站汲取的能量是多少。

1. #include<bits/stdc++.h>
2. using namespace std;
4. int main(){
5.     int n;
6.     cin>>n;
7.     vector<int> H(n);
8.     vector<int> val(n);
9.     for(int i=0;i<n;i++)cin>>H[i]>>val[i];
11.     vector nextG=[](vector<int> v){
12.         int n=v.size();
13.         vector<int> res(n,-1);
14.         stack<int> sta;
15.         for(int i=0;i<n;i++){
16.             while(not empty(sta) and v[sta.top()]<v[i]){
17.                 res[sta.top()]=i;
18.                 sta.pop();
19.             }
20.             sta.push(i);
21.         }
22.         return res;
23.     }(H);
25.     vector prevG=[](vector<int> v){
26.         int n=v.size();
27.         vector<int> res(n,-1);
28.         stack<int> sta;
29.         for(int i=n-1;~i;i--){
30.             while(not empty(sta) and v[sta.top()]<v[i]){
31.                 res[sta.top()]=i;
32.                 sta.pop();
33.             }
34.             sta.push(i);
35.         }
36.         return res;
37.     }(H);
39.     vector<int> ans(n);
40.     for(int i=0;i<n;i++){
41.         if(~nextG[i])ans[nextG[i]]+=val[i];
42.         if(~prevG[i])ans[prevG[i]]+=val[i];
43.     }
44.     cout<<*max_element(ans.begin(),ans.end())<<endl;
45. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金