算法数据结构

发布日期: 2023-07-23

更新日期: 2024-12-20

单调栈即满足单调性的栈结构。

单调栈则主要用于 $O\left(n\right)$ 解决 NGE 问题——对序列中每个元素，找到下一个比它大的元素。简单说来，单调栈是满足从栈顶到栈底的元素是单调的栈。

数据结构

单调递增/递减栈是根据出栈后的顺序来决定的_{栈内顺序[1, 2, 6]，出栈后顺序[6, 2, 1]，这就是单调递减栈}

使用场景：单调栈一般用于解决第一个大于 xxx 或者第一个小于 xxx 这种题目。

数据操作

数据插入

将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。

例如，栈中自顶向下的元素为 {0,11,45,81}。

插入元素 14 时为了保证单调性需要依次弹出元素 0,11，操作后栈变为 {14,45,81}。

代码

寻找每个元素右侧的首个比他大的数

int[] res = new int[nums.length];  // 结果数组
Stack<Integer> s = new Stack<>(); // 初始化单调栈
for(int i = 0; i < nums.length; ++i){
    if(stack.isEmpty()){  // 单调栈为空，直接进栈
        stack.push(i);  // 进栈的是下标而不是数据
    }else{  // 栈不为空
        while(!stack.isEmpty() && nums[stack.peek()] < nums[i]){  // 数组值与栈顶下标对应值比较
            res[stack.peek()] = i - stack.pop();  // 出栈
        }
        stack.push(i);
    }   
}