Stack实现O(1)的Min和Max

栈（Stack）Pop和Push操作只需要对栈顶元素进行操作，就不多加描述了。那么对于Max和Min操作，怎么保证O(1)的时间复杂度?最直接想到的就是设置两个标记位，最小值的最大值，在push和pop的时候更新两个值。那么怎么更新呢，怎么保证最大值和最小值弹出之后还能正确获取到当前所有元素中的最大值和最小值呢？请看下文：

辅助最大值栈SM

算法描述

type Stack Struct{
	data []int
}

var SMax *Stack = new(Stack)

• push: 如果当前元素大于等于辅助栈的栈顶元素或者辅助栈为空，那么当前元素push到辅助栈中
• pop: 如果当前元素等于辅助栈的栈顶元素，那么从辅助栈中弹出当前元素

举个例子

如果有1，3，6，1，12，512，12，5121，121，412数据放入栈中

Step-1. 元素1入栈，当前SM栈为空，SM栈也同步更新

Stack: 1
SMax: 1

Step-2. 元素3入栈，3 > 1，SMax栈也同步更新

Stack: 1, 3
SMax: 1, 3

Step-3. 元素6入栈，6>3，SMax栈也同步更新

Stack: 1, 3, 6
SMax: 1, 3, 6

…此处省略更多步骤

最大值标记法

第一种方式利用辅助栈来标记当前最大值和上一个最大值，并利用栈来实现O(1)复杂度。但是根据上述的例子，可以看到如果插入的元素是依次增大，那么耗费2N+1空间才能实现栈的最大值和最小值在O(1)复杂度。现在介绍的方法，能够很好的减少空间耗费，并保证O(1)时间复杂度。

算法描述

type Stack struct {
	data []int
	max  int // default = math.MinInt32
}

• push: 将(当前元素-Max)放入栈中；如果当前元素大于Max，用当前元素替换Max
• pop: 如果栈顶元素>0，弹出Max，用Max-栈顶元素替换Max；否则弹出Max+栈顶元素

再举个例子

如果有5, 23, 12, 499, 45, 20, 60入栈

Step-1. 元素5-Max入栈，5 > math.MinInt32, 更新Max=5

Stack: 5-math.MinInt32
Max: 5

Step-2. 元素23-5入栈，23 > Max=5, 更新Max=23

Stack: 5-math.MinInt32, 18
Max: 23

Step-3. 元素12-23入栈，5 !> Max=23, 不更新Max

Stack: 5-math.MinInt32, 18, -11
Max: 23

Step-4.-11 < 0, 元素Max+-11 = 12 弹出, 不更新Max

Stack: 5-math.MinInt32, 18
Max: 23

Step-5. 18 < 0, 元素Max弹出, 更新Max = (Max-18)

Stack: 5-math.MinInt32
Max: 5

…此处省略更多步骤

最小值的引导

上述的两种方法，只是描述了最大值的思路。

对于第一种思路来说，推导到最小值身上就是SMin辅助栈，push的时候，如果当前元素小于等于SMin栈定元素，便将当前元素push到SMin中去；同理pop的时候，如果当前元素等于SMin的栈顶元素，也将当前元素从SMin中弹出。

第二种的思路是，通过栈中的元素来标记最大值。推导到最小值上来说就是：

• push: 将(当前元素-Min)放入栈中；如果当前元素小于Min，用当前元素替换Min
• pop: 如果栈顶元素<0，弹出Min，用Min-栈顶元素替换Min；否则弹出Min+栈顶元素

问题

如果考虑采用第二种方式来同时实现最小值和最大值的话…？