一、前言

  最近依旧在刷《剑指offer》的题目,然后今天写到了一道蛮有意思的题目,叫做包含min函数的栈,解题思路有点妙,写篇博客记录一下。


二、描述

  这道题目的描述是:定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂度应为O(1))

  然后这题给出的原始代码如下,具体方法代码需要自己补充:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 - minValuenode就是当前要入栈的元素,而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这些操作的具体代码我就不自己写了;

 思路一实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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();
}
}

 思路二实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
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() {
if(dataStack.isEmpty()) {
throw new EmptyStackException();
}
Integer val = dataStack.pop();
// 若当前出栈的值是最小值,则计算出上一个最小值并更新
if(val < 0) {
minValue = minValue - val;
}
}

/**
* 查看栈顶元素
*/
public int top() {
if(dataStack.isEmpty()) {
throw new EmptyStackException();
}
Integer val = dataStack.peek();
// 若栈顶元素不是最小值,则计算元素的实际值
return val < 0 ? minValue : minValue + val;
}

/**
* 返回栈中最小值
*/
public int min() {
if(dataStack.isEmpty()) {
throw new EmptyStackException();
}
return minValue;
}
}