单调栈

单调栈找最近

用于找每个数左/右边最近的比它小/大的数

(1)左边最近的小于它的数

从1~n遍历

序列应该是单调递增（保证栈头为最优解）

所以如果出现向下趋势就不断出栈

while(tt && x <= stk[tt])
    tt--;
//具体操作
//…… //把栈头作为答案保存
stk[++tt]=x;//把该元素入栈

(2)左边最近的大于它的数

从1~n遍历

序列应该是单调递减

所以如果出现向上趋势就不断出栈

while(tt && x >= stk[tt])
    tt--;
//具体操作
//…… //把栈头作为答案保存
stk[++tt]=x;//把该元素入栈

(3)右边最近的小于它的数

从n~1遍历

序列应该是单调递增

所以如果出现向下趋势就不断出栈

for(int i=n;i>=1;i--){
    while(tt && h[i] <= h[stk[tt]])
      tt--;
    //具体操作
    //…… //把栈头作为答案保存
    stk[++tt]=i;//把该下标入栈
}

(4)右边最近的大于它的数

从n~1遍历

序列应该是单调递减

所以如果出现向上趋势就不断出栈

for(int i=n;i>=1;i--){
    while(tt && h[i] >= h[stk[tt]])
      tt--;
    //具体操作
    //…… //把栈头作为答案保存
    stk[++tt]=i;//把该下标入栈
}

想清楚要找什么

考虑遍历方向

和答案应该是较大的还是较小的

较小的话栈里应该是单调递增这样才能保证栈顶是最合适的答案

较大的话反过来栈里应该是单调递减

单调栈+二分找最远

(1)左边最远的大于它的数

比如对于3来说如果左边已经有了5 在53中间再来一个4是完全没有必要的因为3肯定找到的是那个5 因为更大且更远由此发现是一个不出现递减趋势的序列

但个53中间有个7的话这个7虽然不会被3找到但是它可能会被后面的一个6找到

综上构造一个单调递增的序列

若这个新加的数能保持递增趋势说明不存在比它更大的数没必要去找了直接加进去供后面的数去找

如果不能保持递增趋势就说明左边有一个比它更大的数在这个已有的单调序列中二分找到

#include<bits/stdc++.h>
using namespace std;

const int N=100;
int a[N];
vector<int> stk;
int ans[N];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    //需要注意的一点是 stk存的是下标
    for(int i=1;i<=n;i++){
    	//a[i]>a[stk.back()] 还是 a[i]>=a[stk.back()]
        //加不加等号看题意
        //找严格小于它的数的话 这里加等号 意味着找到它自己
        //找前面小于等于它的数的话 这里不加等号
		if(stk.empty() || a[i]>=a[stk.back()]){//发现该元素比栈顶元素还大（保持单调递增）
            stk.push_back(i);//直接入栈
            ans[i]=i;//记录答案 可能求长度等等
        }
        else{//发现该元素不是最大  那么原单调序列里肯定存在一些比他大的数 二分找到最远的那个
            int l=1,r=stk.size()-1;
            while(l<r){
                int mid=l+r>>1;
                if(a[stk[mid]]>a[i])
                    r=mid;
                else
                    l=mid+1;
            }
            ans[i]=stk[r];
        }
    }

    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}

(2)左边最远的小于它的数

同理现在找最小的数如果本身已经是最小了就没必要找直接加入单调栈保持单调性如果自身不是最小也不做什么踢出操作直接在单调栈里找答案就行只不过它也没必要加进去

#include<bits/stdc++.h>
using namespace std;

const int N=100;
int a[N];
vector<int> stk;
int ans[N];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    for(int i=1;i<=n;i++){
        if(stk.empty() || a[i]<a[stk.back()]){//只要改两处
            stk.push_back(i);
            ans[i]=i;
        }
        else{
            int l=0,r=stk.size()-1;
            while(l<r){
                int mid=l+r>>1;
                if(a[stk[mid]]<a[i]) //只要改两处
                    r=mid;
                else
                    l=mid+1;
            }
            ans[i]=stk[r];
        }
    }

    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}

(3)右边最远的大于它的数

从右边开始枚举罢了 1-n变成n-1即可

找最远的大于若该数是最大的直接加入栈中如果不是再二分找一下

#include<bits/stdc++.h>
using namespace std;

const int N=100;
int a[N];
vector<int> stk;
int ans[N];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    for(int i=n;i>=1;i--){//只需改循环
        if(stk.empty() || a[i]>a[stk.back()]){
            stk.push_back(i);
            ans[i]=i;
        }
        else{
            int l=0,r=stk.size()-1;
            while(l<r){
                int mid=l+r>>1;
                if(a[stk[mid]]>a[i])
                    r=mid;
                else
                    l=mid+1;
            }
            ans[i]=stk[r];
        }
    }

    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}

(4)右边最远的小于它的数

n-1 最小若该数为最小直接加入否则二分找

#include<bits/stdc++.h>
using namespace std;

const int N=100;
int a[N];
vector<int> stk;
int ans[N];
int n;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    for(int i=n;i>=1;i--){
        if(stk.empty() || a[i]<a[stk.back()]){
            stk.push_back(i);
            ans[i]=i;
        }
        else{
            int l=0,r=stk.size()-1;
            while(l<r){
                int mid=l+r>>1;
                if(a[stk[mid]]<a[i])
                    r=mid;
                else
                    l=mid+1;
            }
            ans[i]=stk[r];
        }
    }

    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}

总结

思路上：

代码上：

一个是以当前元素维护单调栈不断剔除里面元素使其保持单调性

一个是判断当前元素是否符合单调栈的特性符合就加入不符合可以直接在栈里找答案

题目

更多题目：

⬅️ 链表相关问题 🏠 00-刷题理模型 ➡️ 仰视奶牛

单调栈

单调栈 找最近

(1)左边 最近的 小于它 的数

(2)左边 最近的 大于它 的数

(3)右边 最近的 小于它 的数

(4)右边 最近的 大于它 的数

单调栈+二分 找最远

(1)左边 最远的 大于它 的数

(2)左边 最远的 小于它的数

(3)右边 最远的 大于它的数

(4)右边 最远的 小于它的数

题目

💬 评论