单调栈

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

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

例子

栈中自顶向下的元素为 [0,11,45,81]
插入元素 14 时为了保证单调性需要依次弹出元素 0, 11
操作后栈变为 [14,45,81]

实现

// 假设数组A从左到右遍历
insert x // x 为数组中某一个元素
// 假设维护的是一个单调递增的栈（自栈顶向下单调递增）
while !stack.empty() && stack.top()<x
    y = stack.pop() // 这也意味着y右侧第一个比y大的元素是x
stack.push(x)

有时候，单调栈或单调队列中不一定存的是实际数字的值，有可能存的是指向实际数字的指针或下标，毕竟有时候实际数字的值可以通过下标访问数组获得，存储下标能保存更多利于计算的信息。比如这些题：

应用

下一个更大元素（原型题）

🟩 496. 下一个更大元素 I - 力扣（LeetCode）

或者前一个更小元素。

在线性时间内求出数组 A 中某元素 x 的下一个更大的元素，即 x 右侧第一个比 x 大的元素的值或下标。

保存关键字符

首先考虑一个简单的问题：给定一个字符串 s，如何去掉其中的一个字符 ch，使得得到的字符串字典序最小呢？答案是：找出最小的满足 s[i]>s[i+1] 的下标 i，并去除字符 s[i]。我们称这样的字符为「关键字符」。

最小栈

🟨 155. 最小栈 - 力扣（LeetCode）

请你设计一个 最小栈 。它提供 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

暴力做法就是每次获取辗转最小值时二分查找最小值，或者另外维护堆结构。但是这样的话，查找的时间复杂度或维护堆的时间复杂度较高。

对于栈来说，如果一个元素 a 在入栈时，栈里有其它的元素 b, c, d，那么无论这个栈在之后经历了什么操作，只要 a 在栈中，b, c, d 就一定在栈中，因为在 a 被弹出之前，b, c, d 不会被弹出。因此，在操作过程中的任意一个时刻，只要栈顶的元素是 a，那么我们就可以确定栈里面现在的元素一定是 a, b, c, d。那么，我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m。

基本做法：双栈

class MinStack {
    Deque<Integer> stack = new LinkedList<>();
    Deque<Integer> m_stack = new LinkedList<>();
    int min = Integer.MAX_VALUE;

    /** initialize your data structure here. */
    public MinStack() {}
    
    public void push(int x) {
        min = Math.min(min,x);
        stack.push(x);
        m_stack.push(min);
    }
    
    public void pop() {
        stack.pop();
        m_stack.pop();
        min = m_stack.peek()==null?min = Integer.MAX_VALUE:m_stack.peek();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return m_stack.peek();
    }
}

如果你觉得上面的代码还不够简洁，你可以去掉全局 min，并在栈初始化时，提前将 Integer.MAX_VALUE 哨兵放入 m_stack 中。

复杂度分析：

时间复杂度：对于题目中的所有操作，时间复杂度均为 $O(1)$ 。因为栈的插入、删除与读取操作都是 $O(1)$ ，我们定义的每个操作最多调用栈操作两次。
空间复杂度： $O(n)$ ，其中 n 为总操作数。最坏情况下，我们会连续插入 n 个元素，此时两个栈占用的空间为 $O(n)$ 。

常数优化：辅助栈维护更少的元素

在基本的做法中，每个 stack 中的元素都对应 m_stack 中一个元素。其实 m_stack 中会有重复的元素放入。

改进后，双栈分工：

数据栈 A ：栈 A 用于存储所有元素，保证入栈 push() 函数、出栈 pop() 函数、获取栈顶 top() 函数的正常逻辑。
辅助栈 B ：栈 B 中存储栈 A 中所有非严格降序元素的子序列，则栈 A 中的最小元素始终对应栈 B 的栈顶元素。此时，getMin() 函数只需返回栈 B 的栈顶元素即可。

辅助栈中元素以「非严格降序」进行排序，防止辅助栈提前弹出最小值：

参考实现：

class MinStack {
    Deque<Integer> stack = new LinkedList<>();
    Deque<Integer> m_stack = new LinkedList<>();

    public MinStack() {
        m_stack.push(Integer.MAX_VALUE);
    }
    
    public void push(int x) {
        stack.push(x);
        if(x<=m_stack.peek()){
            m_stack.push(x);
        }
    }
    
    public void pop() {
        int o = stack.pop();
       
        if(o==m_stack.peek()){
            m_stack.pop();
        }
        
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return m_stack.peek();
    }
}

常数优化：只使用一个栈

我们取消辅助栈，引入全局变量 min，实时维护当前栈中最小值。而唯一的栈结构用来保存入栈时的元素与当前 min 的差值。因此我们最需要关注的地方为：

弹栈时，如何维护好 min
弹栈时，并返回正确的初始元素

class MinStack {
    Deque<Long> stack = new LinkedList<>();
    long min;

    public MinStack() {}
    
    public void push(int x) {
        if(stack.isEmpty()){
            min = x;
            stack.push(0L);
            return;
        }
        long delta = x-min;
        if(delta<0L){
            min = x;
        }
        stack.push(delta);
    }
    
    public void pop() {
        Long o = stack.peek();
       
        if(o<0){
            min = min-o;
        }       
        stack.pop();
    }
    
    public int top() {
        Long o = stack.peek();
        
        return (int)(o>0?o+min:min);
    }
    
    public int getMin() {
        return (int)min;
    }
}