题目链接

思路如下

这题恶心的枚举任意区间的最大值及次最大值，正常的操作是，是很难实现的，但偏偏有个 单调栈这个动西，能够完成这个任务，跟单调队列相似，有单调递增、递减的栈，这一题我们需要维护的是：递减栈。

对于这个单调递减栈：指的是从从栈的底部 ——> 到栈顶元素值逐渐递减。

⚠️对于栈的push操作：

栈为空的时候：直接压入元素
栈不为空的时候：1. 当所压入的元素小于栈顶的元素的时候，直接压入该元素。。。。2.当所压入的元素大于栈顶的元素的时候，如果这个时候，我们把这个元素直接压入队列了，那么会破坏栈的单调递减性，所以我们应该把在栈内比我们将要压入的元素大的全部弹出pop，然后在将该元素压入栈。

题解如下

#include<iostream>

#include<stack>

using namespace std;

const int Len = 1e5 + 5;

int ar[Len];

int main()

{

    int n;

    scanf("%d",&n);

    for(int i = 0; i < n; i ++)

        scanf("%d",&ar[i]);

    stack<int> st;

    st.push(ar[0]);

    int ans = -1;

    for(int i = 1; i < n; i ++)

    {

        while(! st.empty() && ar[i] > st.top())

        {

            ans = max(ans , ar[i]^st.top());

            st.pop();

        }

        if(! st.empty())

            ans = max(ans , st.top()^ar[i]);

        st.push(ar[i]);

    }

    printf("%d",ans);

    return 0;

}

巴特西

CodeForces 280B（枚举 + 单调栈应用）

题目链接

思路如下

题解如下

最新文章

热门文章