By

文章目录
  1. 1. 题目
  2. 2. 解题
  3. 3. 代码
  4. 4. 参考

题目

定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。

解题

这道题目的主要难点就是需要的复杂度为O(1)，也就是说在求最小值的时候无法遍历该栈。
正确地解法就是使用一个辅助栈（数组），为维持当前栈容量下地最小值情况

比如

栈数据
3,5,2,4,1
辅助数据
0,0,2,2,4

将5压入栈的时候，发现上一个栈顶元素下的最小值是3，故这里无法更新最小值，仍旧将当前的最小值置为3（索引位置为0），但是当2压入栈的时候
，可以发展2<3，所以在该类情况下会将当前栈的最小值更新为2（即索引为2）
这种设计在出栈的时候只需要将栈数据的栈顶出掉即可，同样在求最小值的时候只要返回当前辅助数据中索引值在栈数据中的值即可
这样就非常方便地实现了O（1）的要求，同时因为辅助栈是存储索引位置，索引并不会占用很大的内容空间

代码

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
public class MinStack<E extends Comparable<E>> {

	//存储栈的元素
	private Object[] elementData;
	//存储当前栈尺寸下最小元素的位置
	private int[] minPos;
	
	//栈的实际大小
	private int size=0;
	//栈的总容量
	private int capacity=0;
	//栈的默认容量
	private static final int DELAULT_CAPACITY=10;
	
	public MinStack()
	{
		this(DELAULT_CAPACITY);
	}
	
	
	public MinStack(int capacity)
	{
		this.elementData=new Object[capacity];
		this.minPos=new int[capacity];
		
	}
	
	/**
	 * 将数据压入栈
	 * @param e
	 */
	public void push(E e)
	{
		ensureCapacity(size+1);
		
		elementData[size]=e;
		//这里来维护最小元素位置的数组
		if(size==0 || e.compareTo((E)elementData[minPos[size-1]])<0)
		{
			//更新栈的最小元素
			minPos[size]=size;
		}else{
			minPos[size]=minPos[size-1];//保持原来的为最小
		}
		size++;
		
	}
	
	/**
	 * 出栈  直接出
	 * @return
	 * @throws EmptyStackException
	 */
	public E pop() throws EmptyStackException
	{
		if(size<=0)
			throw new EmptyStackException();
		
		size--;
		return (E)elementData[size];
	}
	
	/**
	 * 取最小值  直接在辅助的数组上取值即可
	 * @return
	 * @throws EmptyStackException
	 */
	public E min() throws EmptyStackException
	{
		if(size<=0)
			throw new EmptyStackException();
		
		return (E)elementData[minPos[size-1]];
	}
	
	/**
	 * 确保容量足够
	 * @param minCapacity
	 */
	public void ensureCapacity(int minCapacity)
	{
		if(minCapacity>capacity)
		{
			//需要扩容
			int newCapacity = minCapacity + (minCapacity >> 1);
			elementData=Arrays.copyOf(elementData, newCapacity);//拷贝数组
			minPos=Arrays.copyOf(minPos, newCapacity);
			capacity=newCapacity;//更新容量
		}
	}
	
	public void printStack()
	{
		System.out.println("\r\n栈数据");
		for(int i=0;i<size;i++)
			System.out.print(this.elementData[i]+",");
		
		System.out.println("\r\n辅助数据");
		for(int i=0;i<size;i++)
			System.out.print(this.minPos[i]+",");
		
		System.out.println();
	}

}

实现这个栈的代码如上，使用main函数的测试如下

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
	MinStack<Integer> minStack=new MinStack<Integer>();
	minStack.push(3);
	minStack.push(5);
	minStack.push(2);
	minStack.push(4);
	minStack.push(1);
	minStack.printStack();
	System.out.println("最小值:"+minStack.min());
	minStack.pop();
	minStack.printStack();
	System.out.println("最小值:"+minStack.min());
}

最终就可以打印出:

栈数据
3,5,2,4,1,
辅助数据
0,0,2,2,4,
最小值:1

栈数据
3,5,2,4,
辅助数据
0,0,2,2,
最小值:2

参考

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

文章目录
  1. 1. 题目
  2. 2. 解题
  3. 3. 代码
  4. 4. 参考