单调栈

作者: 安安zoe | 来源:发表于2017-10-16 15:13 被阅读0次

    引入:一道编程题

    给一个长度为N的个不相同的序列,找出所有区间中最大值和第二大数异或值最大的值;

    分析:对于所有区间只需要找其最大值和第二大数,所以对于很多区间的结果是重复的,对于每一个数,它起作用的区间只有在其前面最多只有一个数是大于它的,可以用一个单调递减栈来做,对于每一个新的数a[i],在它前面第一个大于它的数 a[j]和第二个大于它的数之间的数到 a[i] 的区间的数的最大值和第二大数为a[j] , a[i],只需要找a[i],a[j]的所有区间所有情况.

    #include<cstdio>
    #include<cstring>
    #include<iostream>
    using namespace std;
    
    const int maxn = 100010;
    int s[maxn];
    int main()
    {
        int n;
        while (~scanf("%d", &n))
        {
            int top = -1;
            int ans = 0;
            for (int i = 1; i <= n; i++)
            {
                int t;
                scanf("%d", &t);
                // top 栈顶 单调递减栈
                while (top != -1 && s[top] < t){ 
                    ans = max(ans, t^s[top--]); 
                }
                if (top != -1)
                    ans = max(ans, t^s[top]);
                s[++top] = t;
            }
            printf("%d\n", ans);
        }
        return 0;
    }
    
    

    单调栈的性质

    • 栈内的元素,按照某种方式排序下(单调递增或者单调递减),如果新入栈的元素破坏了单调性,就弹出栈内元素,直到满足单调性。

    • 作用:可以很方便求出某个数的左边或者右边第一个比它大或者小的元素,时间复杂度为O(N)

    • 进展操作(单调递增栈):每次进栈检验栈顶元素和进栈元素e的大小,如果栈顶元素小于e,则直接入栈,如果大于等于e,则出栈,直到栈空或者栈顶元素小于x

    • 例子:1 4 3 6 0

      1. 1入栈:(1)
      2. 4要入栈,4大于1,则入栈:(1,4)
      3. 3要入栈,弹出4,3进栈(1,3)
      4. 6要入栈,入栈:(1,3,6)
      5. 0要入栈:(0)

      这里可以是单调递增栈,从左向右读入数据,可以看到我们可以很容易找到这个数左边第一个比它小的数

    例题

    https://segmentfault.com/a/1190000004023326

    参考:

    相关文章

      网友评论

          本文标题:单调栈

          本文链接:https://www.haomeiwen.com/subject/mpkhuxtx.html