目录

题目描述解法11 压入栈（push）2 弹出栈（pop）3 查询最小值（getMin）4 Java代码演示 解法21 压入栈（push）2 弹出栈（pop）3 查询最小值（getMin）4 Java代码演示 解法1 VS 解法2

题目描述

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

要求：

pop、push、getMin操作的时间复杂度都是O(1)；设计的栈类型可以使用现成的栈结构。

解法1

使用两个栈协作完成：一个栈用来保存当前栈中的元素，其功能和一个正常的栈没有区别，这个栈记为stackData；另一个栈用于保存每一步的最小值，这个栈记为stackMin。

1 压入栈（push）

1 将被压入数据为newNum，先压入stackData。 2 接着判断stackMin是否为空：

如果为空，则将newNum压入stackMin；如果不为空，比较newNum和stackMin的栈顶元素：如果newNum小于等于stackMin栈顶元素，则将newNum压入stackMin；否则不进行任何操作。

2 弹出栈（pop）

1 先在stackData中弹出栈顶元素，记为value。 2 比较value和当前stackMin的栈顶元素的大小：如果value等于stackMin栈顶元素，stackMin弹出栈顶元素；如果大于，不执行任何操作。 3 返回value。

3 查询最小值（getMin）

stackMin的栈顶元素始终是当前stackData中的最小值，所以获取stackMin的栈顶元素即可。

4 Java代码演示

import java.util.Stack; public class MyStack1 { // 栈内部定义两个私有栈，stackData用来存放数据，stackMin在与stackData的对照中存放最小数据 private Stack<Integer> stackData; private Stack<Integer> stackMin; // 在构造函数中初始化stackData和stackMin public MyStack1() { this.stackData = new Stack<Integer>(); this.stackMin = new Stack<Integer>(); } public void push(int newNum) { // 如果stackMin为空，压入stackMin if(this.stackMin.isEmpty()) { this.stackMin.push(newNum); } // 如果stackMin不为空且newNum小于等于stackMin的栈顶元素，压入stackMin else if (newNum <= this.stackMin.peek()) { this.stackMin.push(newNum); } // 无论如何，将newNum压入stackData栈中 this.stackData.push(newNum); } public int pop() { // 如果stackData为空，抛出异常 if(this.stackData.isEmpty()) { throw new RuntimeException("Your stack is empty."); } // 弹出stackData栈顶元素，如果stackData的栈顶元素等于stackMin的栈顶元素，则弹出stackMin栈顶元素，否则不弹出 int value = this.stackData.pop(); if(value == this.stackMin.peek()) { this.stackMin.pop(); } // 返回stackData栈顶元素 return value; } public int getMin() { // 如果stackData为空，抛出异常 if(this.stackMin.isEmpty()) { throw new RuntimeException("Your stack is empty."); } // 返回stackMin栈顶元素 return this.stackMin.peek(); } } public class Demo { public static void main(String[] args) { // 创建一个栈对象 MyStack1 test = new MyStack1(); // 压入元素 test.push(3); test.push(4); test.push(5); test.push(1); test.push(2); test.push(1); test.push(-1); // 弹出元素 test.pop(); // 获取最小元素 System.out.println(test.getMin()); } } // 运行结果 1

解法2

使用两个栈协作完成：一个栈用来保存当前栈中的元素，其功能和一个正常的栈没有区别，这个栈记为stackData；另一个栈用于保存每一步的最小值，这个栈记为stackMin。

1 压入栈（push）

1 将被压入数据为newNum，先压入stackData。 2 接着判断stackMin是否为空：

如果为空，则将newNum压入stackMin；如果不为空，比较newNum和stackMin的栈顶元素：如果newNum小于等于stackMin栈顶元素，则将newNum压入stackMin；否则将stackMin的栈顶元素取出，并再一次压入stackMin。

2 弹出栈（pop）

1 先在stackData中弹出栈顶元素，记为value。 2 弹出stackMin的栈顶元素。 3 返回value。

3 查询最小值（getMin）

stackMin的栈顶元素始终是当前stackData中的最小值，所以获取stackMin的栈顶元素即可。

4 Java代码演示

import java.util.Stack; public class MyStack2 { // 栈内部定义两个私有栈，stackData用来存放数据，stackMin在与stackData的对照中存放最小数据 private Stack<Integer> stackData; private Stack<Integer> stackMin; // 在构造函数中初始化stackData和stackMin public MyStack2() { this.stackData = new Stack<Integer>(); this.stackMin = new Stack<Integer>(); } public void push(int newNum) { // 如果stackMin为空，压入stackMin if(this.stackMin.isEmpty()) { this.stackMin.push(newNum); } // 如果stackMin不为空且newNum小于等于stackMin的栈顶元素，压入stackMin else if (newNum <= this.stackMin.peek()) { this.stackMin.push(newNum); } // 否则将stackMin的栈顶元素取出，并再一次压入stackMin else { int newMin = this.stackMin.peek(); this.stackMin.push(newMin); } // 无论如何，将newNum压入stackData栈中 this.stackData.push(newNum); } public int pop() { // 如果stackData为空，抛出异常 if(this.stackData.isEmpty()) { throw new RuntimeException("Your stack is empty."); } // 弹出stackData栈顶元素，弹出数据记为value,同时弹出stackMin栈顶元素 int value = this.stackData.pop(); this.stackMin.pop(); // 返回stackData栈顶元素 return value; } public int getMin() { // 如果stackData为空，抛出异常 if(this.stackMin.isEmpty()) { throw new RuntimeException("Your stack is empty."); } // 返回stackMin栈顶元素 return this.stackMin.peek(); } } public class Demo { public static void main(String[] args) { // 创建一个栈对象 MyStack2 test = new MyStack2(); // 压入元素 test.push(3); test.push(4); test.push(5); test.push(1); test.push(2); test.push(1); test.push(-1); // 弹出元素 test.pop(); // 获取最小元素 System.out.println(test.getMin()); } } // 运行结果 1

解法1 VS 解法2

解法1和解法2都设计了两个栈，一个用来存放数据，另一个保存每一步的最小值；时间复杂度都是O(1)，空间复杂度都是O(n);解法1stackMin压入时稍省空间，弹出时稍费时间；解法2stackMin压入时稍费空间，弹出时稍省时间。