本文共 2007 字，大约阅读时间需要 6 分钟。

题目地址：

用栈实现一个数据结构可以实现如下操作：

1、将数据进栈，出栈，并且按照FILO的原则； 2、查看栈顶，查看栈中最大值； 3、删掉栈中最大值。

基本思路是用两个栈，其中一个栈$s_1$存原本的数据，另开一个单调栈$s_2$，存所有遇到的最大值。这样即使在原栈中的最大值pop掉，也能通过在第二个栈里找到剩余数字的最大值。具体考虑如下：

1、push的时候，对于$s_1$只需直接进栈即可，对于$s_2$，要看一眼新来的数是否大于等于栈顶，如果是，则进栈，否则不进栈。这样的考虑在于记录当前栈中的最大值，注意，即使新来的数等于栈顶，仍然需要进栈，这是为了记录这个最大值出现了多少次； 2、pop的时候，对于$s_1$仍然是直接pop，对于$s_2$则需要看一下从$s_1$里pop的是否是当前最大值，如果是，则将$s_2$也pop，否则不动； 3、top和peekMax就直接看两个栈的栈顶即可； 4、对于popMax，需要先用一个变量存一下当前最大值是多少，也就是$s_2$的栈顶，然后另外开一个临时栈，把$s_1$上面的数字全倒进去，直到pop出$s_1$里的最大值，此时也要pop出$s_2$，然后再调用1里面的push方法把数字再进栈。注意，一定要调用MaxStack的push方法而不是调用$s_1$的push方法，这是因为倒出来的数字里可能有次大值，而那个单调栈只是存放了$s_1$从最大值到栈底的数字里的最大、次大等等值，并没有存放最大值到栈顶的数字信息；调用push的目的就是把这些信息也存到$s_2$里。代码如下：

import java.util.ArrayDeque;import java.util.Deque;public class MaxStack {
           Deque
   
     stk, maxStk;        public MaxStack() {
           stk = new ArrayDeque<>();        maxStk = new ArrayDeque<>();    }        public void push(int x) {
           stk.push(x);        if (maxStk.isEmpty() || maxStk.peek() <= x) {
               maxStk.push(x);        }    }        public int pop() {
           int x = stk.pop();        if (!maxStk.isEmpty() && x == maxStk.peek()) {
               maxStk.pop();        }                return x;    }        public int top() {
           return stk.peek();    }        public int peekMax() {
           return maxStk.peek();    }        public int popMax() {
           Deque
    
      tempStk = new ArrayDeque<>();        int x = maxStk.pop();        while (!stk.isEmpty() && stk.peek() < x) {
               tempStk.push(stk.pop());        }                stk.pop();        while (!tempStk.isEmpty()) {
           	// 调用MaxStack的push方法，把倒出来的数字再倒回去            push(tempStk.pop());        }                return x;    }}
    
   

空间$O(n)$，时间复杂度只有popMax是$O(n)$，其余都是$O(1)$。

算法正确性证明的关键在于，证明$s_2$存放的是$s_1$里从最大值到栈底的最大、次大等等值，出现次数一样并且单调递减排列。可以用数学归纳法，这里省略。

转载地址：http://dsds.baihongyu.com/