Java实现最小栈的两种方式——时间复杂度O(1)
一、前言
最近依旧在刷《剑指offer》的题目，然后今天写到了一道蛮有意思的题目，叫做包含min函数的栈，解题思路有点妙，写篇博客记录一下。
二、描述
这道题目的描述是：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
然后这题给出的原始代码如下，具体方法代码需要自己补充：
import java.util.Stack;
public class Solution {
public void push(int node) {
}
public void pop() {
}
public int top() {
}
public int min() {
}
}三、思路
看到这题，大多数人的第一反应应该就是：在类中声明一个变量minVal，记录当前栈中的最小值，然后在调用min方法时将这个最小值返回。但是仔细想一想，会发现这种办法是不可行的，因为如果执行了pop操作，将最小值出栈了，那我们怎么知道，剩下的元素中最小的是哪个，如何找到它从而去更新变量minVal呢？或许你认为可以在最小值出栈后，遍历剩下的元素，重新找出新的最小值。这样确实可以，相比于每次调用min都遍历一遍找最小值这种最笨的方法要好一些，但是别忘了，题目要求我们这个算法的时间复杂度是O(1)，而且在面试中，这种方法是拿不到分的。所以，我们需要找出更加高效的算法。
3.1 时间复杂度O(1)，空间复杂度O(n)的实现方式
提高时间效率的一个常用方法就是牺牲空间换取时间，这里也可以使用这种办法。我们可以定义一个辅助栈minStack，帮助我们记录最小值。在我们的类中，需要有两个栈，一个就是我们用来存值的栈dataStack，另外一个就是帮助我们维护最小值的栈minStack。
push入栈操作有以下两种情况：
- dataStack为空：此时，栈中没有元素，我们将push传入的参数直接放入到
dataStack以及minStack中； - dataStack不为空：此时，将push操作传入的参数先放入
dataStack中，然后判断这个元素与minStack的栈顶元素谁更大，若这个参数小于或等于minStack的栈顶元素，我们就将它加入到minStack中，否则minStack不变；
这样，我们就可以保证，minStack的栈顶元素，一定是当前栈中最小的元素，而当我们调用min方法时，直接返回minStack的栈顶元素就行了。
与push操作相对应的，pop出栈操作，也有两种情况：
- 出栈的元素大于栈中最小值：此时
dataStack的栈顶元素出栈，而minStack不变； - 出栈的元素等于栈中最小值：此时
dataStack的栈顶元素出栈，同时，minStack的栈顶元素也出栈；
这样做有什么意义呢？很简单，这个minStack里面的元素是怎么来的？如果当前入栈的元素小于等于最小值（即minStack的栈顶元素），我们就把他加入到minStack中；这样一路下来，minStack中的元素一定是单调递减的，而且栈顶元素一定是dataStack中的最小值，而栈顶元素的下一个元素，一定是所有元素中的第二小值，再往下就是第三小值，第四小值......依次类推（这里好好理解一下）。所以，如果我们现在出栈的值，和minStack的栈顶元素（即最小值）相等，那我们就让minStack的栈顶元素出栈，然后神奇的事情发生了：原来的第二小值现在变成了minStack的栈顶元素，而原来的最小值出栈后，第二小值就是新的最小值了；通过这种方式，我们就成功的解决了之前说过的，最小值出栈后，无法立即找到新最小值的问题；
栈中值重复引发的问题
这里还有一个问题，就是：为什么也在进行push时，小于等于最小值的元素需要放入minStack中，而不是小于？这是因为，栈中可能存在重复的值，而最小值也可能有重复。比如说，【1，2，3，1】依次入栈，而第一次入栈的1就是最小值，第四个数也同样为1，它处在栈顶。假设我们使用的是小于，而不是小于等于，则四个数入栈后，minStack的值为【1】。此时，若栈顶元素1出栈，我们检测到出栈的数和最小值1相等，于是我们就让minStack的栈顶元素出栈，然后minStack就为空了，而dataStack是【1，2，3】。可是我们看的出来，栈中的最小值应该还是1，因为1在栈中出现了两次。此时就产生了问题，我们现在已经找不到最小值了。
所以，为了防止这种情况发生，我们在push操作时，检测到当前入栈的元素小于等于最小值时，就需要将它加入minStack中，这时我们再看上面的例子：当四个数都入栈后，minStack的情况是【1，1】，dataStack为【1，2，3，1】，而此时，dataStack的栈顶元素1出栈，minStack的栈顶也出栈，则dataStack变成【1，2，3】，而minStack变成【1】，minStack的栈顶依旧是dataStack中的最小元素1，巧妙避免了上面的问题。
3.2 时间复杂度O(1)，空间复杂度O(1)的实现方式
这道题，我在网上找别人的博客，发现基本上所有人都是上面这种实现方式，但是我还找到一篇博客，有另外一种实现方式，且时间复杂度和空间复杂度都为O(1)。可以说这种实现方式更加的妙，要让我来想，我估计一辈子也想不出这种方法。下面我就来简单介绍一下。
这个新思路实际上就是我们刚开始看到这题时候所想的思路：设置一个变量minValue，记录当前栈中的最小值，然后在调用min方法的时候，直接返回就可以了。但是我们前面也说过，这种方法有一个问题，就是当最小值出栈后，我们如何能够知道剩下的数中，最小值是哪一个，也就是找到上一个最小值。而接下来要讲的思路非常巧妙的解决了这个问题。
首先，在我们自定义的栈中，需要两个属性，一个就是和第一个思路一样的dataStack，而另一个就是minValue，用来存储栈中当前的最小值。可是，这里的dataStack存储的不是加入栈中的元素，我们在dataStack中放的，是当前入栈的元素与当前最小值的差值，即diff = node - minValue（node就是当前要入栈的元素，而minValue是当前栈中的最小值）。然后，这个差值diff我们分两种情况处理：
- diff < 0：差值
diff小于0，根据计算公式可知，当前入栈的元素，小于栈中的最小值，于是我们将最小值minValue更新为当前入栈的元素，并将diff加入dataStack中； - diff >= 0：差值
diff大于等于0，表示当前入栈的元素，大于等于栈中的最小值，则最小值minValue不需要改变；
以上即是入栈push时要进行的操作，而出栈pop时也需要分情况考虑：
- 栈顶元素 < 0：若当前栈顶的元素小于0，表示什么？从上面的描述我们知道，这表示这个元素入栈时，小于当时的最小值，所以它就是当前的最小值，于是
minValue记录的就是当前要出栈的元素；而minValue出栈后，我们如何找到剩下元素中的最小值呢？我们知道，当前栈顶的值是通过diff = node - minValue算出来的，而我们又知道当前的minValue就是这个公式中的node，于是我们就可以知道，minValue（之前） = node - diff = minValue（现在）- diff，通过这个公式，我们成功的获得了上一个最小值（太巧妙了）； - 栈顶元素 >= 0：此时说明当前要出栈的元素不是最小值，所以我们可以根据公式
diff = node - minValue得出，这个元素的实际值node = diff + minValue；
就这样，我们成功的解决了最开始说的，最小值出栈后，无法找到上一个最小值的问题。但是我们上网搜索发现，很少有博客分享这种思路，要说原因，可能是因为这种思路存在一个比较致命的bug。
数据溢出造成的问题
我们试想这样一种情况，假设我们需要在栈中依次放入两个数，【2147483647， -2147483648】，首先，我们在栈中放入2147483647，此时栈中只有一个数，所以最小值就是2147483647。然后我们再向栈中加入 -2147483648，此时，我们需要计算它与最小值的差值，也就是diff = -2147483648 - 2147483647；按我们之前所说，新入栈的值更小，此时应该得到一个负数，上面的公式计算出来也确实是个负数；但是不要忘记，int是有范围的，而上面的公式计算的结果超过了int所能存储的最小值，造成数据溢出，得到的结果是一个 1，是个正数，于是产生了错误的结果，这个思路自然gg。
为了解决这个问题，我们可以用long代替int存储每一个元素，但是这样每个元素的存储空间就扩大了一倍。而这个思路相对于第一个思路的好处就是不需要开辟辅助栈，节省空间，如果改为了long，那这个思路的优势也将不复存在，并且如果我们想在栈中存long类型的值呢，难道要用BigInteger吗？所以华而不实可能就是这个思路没有传播开来的原因吧。当然，这个思路还是非常巧妙的，学习一下也挺好，如果面试中遇到这个题，说出这种思路，也是一个加分项嘛。
四、代码
下面就是上述思路的实现，偷懒了点懒，下面的代码我直接使用了Java自带的栈来实现，主要是关注最小栈的实现思路，push或者pop这些操作的具体代码我就不自己写了；
思路一实现
import java.util.Stack;
public class Solution {
private Stack<Integer> dataStack = new Stack<>();
private Stack<Integer> minStack = new Stack<>();
/**
* 入栈操作
*/
public void push(int node) {
// 判断是否需要更新minStack
if(dataStack.isEmpty() || minStack.peek() >= node) {
minStack.push(node);
}
// 将元素放入dataStack
dataStack.push(node);
}
/**
* 出栈操作
*/
public void pop() {
// 若栈不为空才执行出栈
if(!dataStack.isEmpty()) {
// 若当前出栈的元素，等于栈中的最小值（即minStack的栈顶）
// 则minStack的栈顶出栈
if(dataStack.pop() == minStack.peek()) {
minStack.pop();
}
}
}
/**
* 查看栈顶元素
*/
public int top() {
return dataStack.peek();
}
/**
* 返回栈中最小值
*/
public int min() {
// 返回最小值，即minStack的栈顶元素
return minStack.peek();
}
}思路二实现
import java.util.Stack;
import java.util.EmptyStackException;
public class Solution {
// 存储diff
private Stack<Integer> dataStack = new Stack<>();
// 存储当前栈中的最小值
private Integer minValue;
/**
* 入栈操作
*/
public void push(int node) {
// 栈为空
if (dataStack.isEmpty()) {
minValue = node; // 最小值就是第一个入栈的值
dataStack.push(0); // 而它与当前最小值的差值为0
}else {
Integer diff = node - minValue; // 计算差值
dataStack.push(diff);
// 若新入栈的值小于最小值，则更新最小值
if(diff < 0) {
minValue = node;
}
}
}
/**
* 出栈操作
*/
public void pop() {
Integer val = dataStack.pop();
// 若当前出栈的值是最小值，则计算出上一个最小值并更新
if(val < 0) {
minValue = minValue - val;
}
}
/**
* 查看栈顶元素
*/
public int top() {
Integer val = dataStack.peek();
// 若栈顶元素不是最小值，则计算元素的实际值
return val < 0 ? minValue : minValue + val;
}
/**
* 返回栈中最小值
*/
public int min() {
if(dataStack.isEmpty()) {
throw new EmptyStackException();
}
return minValue;
}
}
