DataStructure

单调栈

nkul · 7月11日 · 2020年 261次已读

顾名思义就是从栈底到栈顶值是单调的!

分为单调递增栈和单调递减栈。

适合题型为:从已经遍历的数中,找距离最近的大于或者小于自身的数!

左边最近的数

考虑以下问题:

输入: 3 ,4,2,7,5

求:每个数的左边第一个比他小的数,没有则输出-1;

输出:-1,3,-1,2,2

在使用暴力破解法时,对于第i个数,循环左边数,找到比a[i]小的即可!

for(int i = 0;i < n;i++){
    for(int j= i-1;j >= 0;j--){
        if(a[j] < a[i]){
            cout << a[j];
            break;
	}
    }
}

实际上在暴力做法中,对于这样的一个序列a[x]>a[y],肯定会先选出a[y],永远不会选出a[x]。也就是说逆序对不会对结果造成影响。

从而在第一层遍历时,用一个栈,因为最终a[i]也是要放入栈顶,因此若栈顶元素大于a[i]形成逆序对,栈顶元素将不影响结果,删掉即可。找第i个元素的左边最近的数时,从栈顶找时,遇到大于等于a[i]的都要删掉!

/**
 * @Author:nkul
 */

#include 
using namespace std;
void func(int a[],int b[],int n){
    //数组模拟栈,tt指向栈顶元素,-1即空栈 
    int stk[n],tt=-1;
    for(int i=0;i=0 && stk[tt]>=a[i]) tt--;
        //如果栈不为空,那么栈顶就是最左最近小于a[i]的数
        if(tt>=0) b[i] = stk[tt];
        //否则就返回-1
        else b[i] = -1;
        //最后入栈
        stk[++tt] = a[i]; 
    }

}
int main()
{
    int a[]={3,4,2,7,5};
    int b[5];
    func(a,b,5);
    for(int i=0;i<5;i++){
        cout<

1、在上面的代码中,使用了数组去模拟栈,栈顶指针用tt指向!

2、如果要找左边最近较大的元素,将while(tt>=0 && stk[tt]>=a[i])改成while(tt>=0 && stk[tt]<=a[i])即可!

相关题目

LeetCode-739 每日温度

2020-7-11 0



0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!