数据结构与算法之栈的最小值
程序员文章站
2022-03-04 21:08:04
...
题目:
实现一个特殊的栈,在实现栈功能基础上,并实现返回栈的最小值要求:
pop,push,getMin方法的时间复杂度O(1)
设计的栈类型可以使用现成的栈结构
Java的Stack类
Java的Stack类:
1. boolean empty()——测试堆栈是否为空。
2. Object peek( )——查看堆栈顶部的对象,但不从堆栈中移除它。
3. Object pop( )——移除堆栈顶部的对象,并作为此函数的值返回该对象。
4. Object push(Object element)——把项压入堆栈顶部。
5. int search(Object element)——返回对象在堆栈中的位置,以 1 为基数。
代码
package cn.scnu.stack;
/**
* 题目:实现一个特殊的栈,在实现栈功能基础上,并实现返回栈的最小值
*
* 要求:
* pop,push,getMin方法的时间复杂度O(1)
* 设计的栈类型可以使用现成的栈结构
*/
import java.util.Stack;
/**
* Java的Stack类
* 1 boolean empty()——测试堆栈是否为空。
* 2 Object peek( )——查看堆栈顶部的对象,但不从堆栈中移除它。
* 3 Object pop( )——移除堆栈顶部的对象,并作为此函数的值返回该对象。
* 4 Object push(Object element)——把项压入堆栈顶部。
* 5 int search(Object element)——返回对象在堆栈中的位置,以 1 为基数。
*/
class MyStack{
private Stack<Integer> stackData = new Stack<>();
private Stack<Integer> stackMin = new Stack<>();
public void push(Integer num){
this.stackData.push(num);
if(this.stackMin.empty()){
this.stackMin.push(num);
}else if (num<=this.getMin()){ //小于等于在于如果两个相等的值,都是最小值,就算弹出其中一个,另一个也是剩下的最小值
this.stackMin.push(num);
}
}
public Integer pop(){
if (this.stackData.empty()) {
throw new RuntimeException("你的栈为空");
}else {
int value = this.stackData.pop();
if(value == this.getMin()){
this.stackMin.pop();
}
return value;
}
}
public Integer getMin(){
if(this.stackMin.empty()){
throw new RuntimeException("你的栈为空!!");
}else{
return this.stackMin.peek();
}
}
}
public class Demo01 {
public static void main(String[] args) {
/*
算法实现原理
*/
MyStack myStack = new MyStack(); //初始化一个栈
/*
添加数据:
1. 将数据添加到栈
2. 判断当前最小值存在不存在
1) 如果不存在,将该数据保存到最小值
2) 如果存在,将该数据和最小值比较,如果该数据小,则替换。
*/
myStack.push(12);
/*
获取最小值:
即,如果最小值栈不为空,那么最小值就是最顶的值
*/
int min = myStack.getMin();
System.out.println(min);
/*
弹出数据:
1. 将数据弹出
2. 如果该数据和最小值相等,则将最小值的栈也弹出一个
3. 如果不想等,那么最小值的栈不变
*/
int num = myStack.pop();
System.out.println(num);
/*
测试
*/
MyStack myStack1 = new MyStack();
for (int i = 10; i >0 ; i--) {
myStack1.push(i);
}
//获取栈的最小值
System.out.println("最小值="+myStack1.getMin());
//获取一个栈的数据
System.out.println(myStack1.pop());
System.out.println("最小值="+myStack1.getMin());
}
}
方法2
class MyStack2{
private Stack<Integer> stackData = new Stack<>();
private Stack<Integer> stackMin = new Stack<>();
public void push(Integer num){
this.stackData.push(num);
if(this.stackMin.empty()){
this.stackMin.push(num);
}else if (num<=this.getMin()){
this.stackMin.push(num);
}else{
//当num>this.getMin,则将上一个最小值重复压入,这样在取出的时候就不需要进行判断了
int newNum = stackMin.peek();
this.stackMin.push(newNum);
}
}
public Integer pop(){
if (this.stackData.empty()) {
throw new RuntimeException("你的栈为空");
}
this.stackMin.pop();
return this.stackData.pop();
}
public Integer getMin(){
if(this.stackMin.empty()){
throw new RuntimeException("你的栈为空!!");
}else{
return this.stackMin.peek();
}
}
}
区别如下
上一篇: 怎样修改php时区