单调栈

2023-12-07

算法 / 单调栈

字数统计: 703 | 阅读时长≈ 2 分钟

单调栈

定义

通常是一维数组,记录任一个元素右(左)边第一个比自身大(小)的元素的下标.

构造

分为正序构造和逆序构造两种方式.

下面我以寻找右边第一个比较自己大的单调栈为例

请注意,本文中所提及的栈的单调情况都是基于栈底到栈顶的顺序.如下图为一个单调减小的栈

正序和逆序只是角度不同,简单来说

正序是把待比较的元素放到栈里,保持栈的单调递减

逆序是把已经比较过的元素放到栈里,保持栈的单调递减

无论正序逆天,都要保证栈的有序,并且需要及时去除无用数据

正序

stack<int>st;//单调递减
vector<int>R;
for(int i = 0; i < nums.size(); i++){
    //现数指用来比较的数,这里是nums[i]
    //如果现数小于栈顶,就一定小于栈里任何数.即直接存入不更新
    //如果现数大于栈顶,就开始把栈顶元素的右大值更新
    //这里的栈放的是左边的元素,等待比较
    while(!s.empty() && nums[i] > nums[s.top()]){
        R[s.top()] = i;
        s.pop();
    }
    st.push(i);
}
//在遍历一次后,有一些数没有找到右大(即右边没有比它大的),还在栈里,这时候要单独处理
while(!s.empty()){
    R[s.top()] = n;
    s.pop;
}

逆序

stack<int>st;//单调递减
vector<int>R;
for(int i =  nums.size() - 1; i >= 0; i--){
    //现数指待比较的数,这里是 nums[i]
    //如果现数大的话,就一直清栈直到,现数比栈里的小或者栈空
    //如果小的话,就跳出while,进行i的更新
    //这里栈放的是右边的元素,用来比较
    while(!s.empty() && nums[i] > nums[s.top()]){
        s.pop();
    }
    if(s.empty()) R[i] = n;//没找到更大的就记为n
    else R[i] = st.top();
    st.push(i);
}

单调栈

定义

构造

正序

逆序

相关题目