Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

【原创】单调栈解析+模板

Where_Free 2019-08-03 00:55:00 阅读数:55 评论数:0 点赞数:0 收藏数:0

单调栈,顾名思义,就是由一组数据。生成一个栈内数值单调递增或递减的栈。

单调栈的意义在于:

在生成单调栈的过程中,可以记录当前数组内的 i 位置往左数,第一个比 i 位置的数大或小的数(大即为递减,小即为递增)(从左端开始入栈的情况下,右端开始入栈即为往右数)

单调递减栈生成过程:

1、在数组中,提取一个数;

2、若栈为空,直接放入,并记录当前原数组位置无最小/最大值;

3、若栈不为空,则将栈顶元素与数组中提取的数值进行比较;

4、若栈顶元素比数组中提取的元素更大,则弹出栈顶元素,继续比较新的栈顶元素,直至栈顶元素小于数组中提取的元素(转跳第5步)或栈空(转跳第2步);

5、若栈顶元素比数组中提取的元素要小,则先记录当前栈顶元素为(参见单调栈意义),后将提取的元素压入栈中。

 

实现代码如下:

 #include <iostream>
 #include <stack>
 using namespace std;
 stack <int> stk;
 int main(){
     int n,list1[],L[];
     cin>>n;
     for(int i=;i<n;i++) cin>>list1[i];
     for(int i=;i<n;i++){
         while(!stk.empty()&&list1[stk.top()]>=list1[i]){//当前栈为单调递减,改为<=为单调递增
             stk.pop();
         }
         if(stk.empty()){
             L[i]=-;
         }
         else L[i]=stk.top();
         stk.push(i);
     }
 }

 

版权声明
本文为[Where_Free]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/Never-Land/p/11291899.html