栈的最大值问题——深入剖析

常数时间求栈的最大值

---

问题描述：

一个栈stack，具有push和pop操作，其时间复杂度皆为O(1)。
设计算法max操作，求栈中的最大值，该操作的时间复杂度也要求为O(1)。可以修改栈的存储方式，push，pop的操作，但是要保证O(1)的时间复杂度，空间时间复杂度无要求。

算法描述：
一个存储所有最大值的栈Sm。

1. 当push入栈的元素大于当前最大元素，将该元素压入最大值栈Sm；
2. Sm栈顶始终保存栈中当前的最大元素；
3. 当前最大元素被pop出栈时，将Sm栈顶的对应最大元素也弹出栈。
   max操作即为获得Sm栈顶最大元素。

假设元素以5,4,1,2,3,10,9,8,6,7,15顺序入栈，则两个栈中存储的元素如下图所示：

常数时间空间求栈的最大值

---

问题描述：
一个整数栈stack，具有push和pop操作，其时间空间复杂度皆为O(1)。
设计算法max操作，求栈中的最大值，该操作的时间空间复杂度也要求为O(1)。可以修改栈的存储方式，push，pop的操作，但是要保证O(1)的时间空间复杂度。

算法描述：
变量Max保存当前最大元素值，初始值为最小整数m。

1. 当push入栈时，将（当前元素-Max）存入栈中，
   若当前元素小于Max，栈中元素为负数；
   若当前元素大于等于Max，栈中元素为非负数，将Max替换为当前元素。

2. 当pop出栈时，
   若栈中元素为负数，则将（栈中元素+Max）弹出栈；
   若栈中元素为非负数，则将Max弹出栈，并将Max替换为（Max-栈中元素）。

3. Max即为当前栈中最大元素值。

主要思路是将最大值以某种方式在原有栈中标记出来，从而减少空间使用。可以用正负数来区分普通元素和最大值元素：
普通元素使用负数存储（元素-Max）；
最大值元素使用非负数存储（New Max - Old Max）；
这样便可在栈中区分普通元素和最大值元素，并可通过Max恢复Old Max。

假设元素以5,4,1,2,3,10,9,8,6,7,15顺序入栈，则两个栈中存储的元素如下图所示：

1. 元素5,4,1,2,3入栈后的情况

   
   

2. 元素10,9,8,6,7入栈后的情况

   
   

3. 元素15入栈后的情况

   
   

4. 元素15出栈时的情况

   
   

5. 元素15出栈后的情况（恢复原有状态）