剑指offer代码解析——面试题21包含min函数的栈

题目:实现一个栈,要求使用O(1)时间获取栈中最小值,O(1)执行pop、push操作。

   分析:要获取栈的最小值,我们首先想到的思路就是使用一个全局变量记录最小值,当元素进栈时和该全局变量进行比较,若小于该全局变量,则更新最小值。这种方法有个致命的缺陷:如果这个最小值出栈了,那么当前栈的最小值该如何确定?

   解决办法:我们可以再创建一个栈b,栈b的高度始终与栈a保持一致,栈顶元素保存当前栈a的最小值。

   入栈:当元素入栈a后,该元素与栈b的栈顶元素进行比较,若小于栈b的栈顶元素,则将该元素入栈b,否则,将栈b原本的栈顶元素再次入栈b。

   出栈:当栈a的栈顶元素出栈时,只需将栈b的栈顶元素也出栈即可。这样,栈b的栈顶元素始终是栈a的最小值。

   首先,我们需要定义以下几个成员变量:

	private int[] stack_a;//栈a底层使用数组存储
	private int[] stack_b;//用于存储最小值的栈
	private int top_a = -1;//栈a的实际深度
	private int top_b = -1;//栈b的实际深度
	private int max;//栈的最大深度

   接着定义构造函数,用于初始化栈:

	/**
	 * 构造函数
	 * @param max 栈允许的最大深度
	 */
	public Stack(int max){
		this.max = max;
		//初始化栈的底层数组
		stack_a = new int[max];
		//初始化用于存储最小值的数组
		stack_b = new int[max];
	}

   然后定义入栈函数:

	/**
	 * 入栈
	 * @param t 入栈的元素
	 * @return 返回入栈操作的结果
	 */
	public boolean push(int t){
		//若栈已满
		if(top_a==max-1){
			System.out.println("栈已满!");
			return false;
		}
		
		//入栈
		{
			//元素首先入栈a
			stack_a[++top_a] = t;
			//当前入栈元素与栈b的栈顶元素比较,若小与栈b的栈顶元素,则入栈b,否则将栈b的栈顶元素再次入栈
			if(top_b==-1 || t<stack_b[top_b])//PS:top_b==-1表示:如果栈b为空,则直接将当前值当作最小值入栈
				stack_b[++top_b]=t;
			else{
				stack_b[top_b+1]=stack_b[top_b];
				top_b++;
			}
		}
		return true;
	}

   最后定义出栈函数:

	/**
	 * 出栈
	 * @return 返回栈顶元素
	 */
	public int pop(){
		//若栈为空
		if(top_a==-1){
			System.out.println("栈为空!");
			return -1;
		}
		
		//栈不为空时可以出栈
		{
			//栈b的栈顶元素出栈
			top_b--;
			//栈a的栈顶元素出栈
			return stack_a[top_a--];
		}
	}

   紧接着我们定义获取最小值函数:

	/**
	 * 获取栈中的最小值
	 * @return 返回栈中最小值
	 */
	public int min(){
		//若栈为空
		if(top_a==-1){
			System.out.println("栈为空!");
			return -1;
		}
		
		//返回最小值
		return stack_b[top_b];
	}

   最后我们进行测试:

	/**
	 * 测试
	 */
	public static void main(String[] args){
		//创建最大容量为10的栈
		Stack stack = new Stack(10);
		
		//栈为空时出栈
		System.out.println("栈为空时出栈:");
		stack.pop();
		
		//入栈
		System.out.println("\n1,2,3,4,5依次入栈:");
		stack.push(5);
		stack.push(4);
		stack.push(3);
		stack.push(2);
		stack.push(1);
		
		//最小值
		System.out.println("\n最小值:"+stack.min());
		
		//出栈
		System.out.println("\n出栈:"+stack.pop());

		//最小值
		System.out.println("\n最小值:"+stack.min());
		
	}

   输出结果如下:

栈为空时出栈: 栈为空! 1,2,3,4,5依次入栈: 最小值:1 出栈:1 最小值:2

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏武培轩的专栏

剑指Offer-包含min函数的栈

package Stack; import java.util.Stack; /** * 包含min函数的栈 * 定义栈的数据结构,请在该类型中实现一个...

2586
来自专栏趣学算法

数据结构 第5讲 顺序栈

       小张终于攒钱买了车,可是他家住在胡同的尽头,胡同很窄,只能通过一辆车,而且是死胡同,每天小张都为停车发愁,回家早了停在里面,早上上班就要让所有的人...

773
来自专栏编程

详解栈及其实现

转自:melonstreet http://www.cnblogs.com/QG-whz/p/5170418.html 栈的特点 栈(Stack)是一种线性存储...

1806
来自专栏desperate633

LintCode 删除排序链表中的重复数字 II题目分析代码

给定一个排序链表,删除所有重复的元素只留下原链表中没有重复的元素。 样例 给出 1->2->3->3->4->4->5->null,返回 1->2->5->...

661
来自专栏C/C++基础

合并两个有序链表

已知两个链表head1和head2各自有序,请把它们合并成一个链表依然有序。结果链表要包含head1和head2的所有节点,即使节点值相同。

772
来自专栏趣学算法

数据结构 第6讲 链栈

进出的一端称为栈顶(top),另一端称为栈底(base)。栈可以用顺序存储,也可以用链式存储。顺序栈和链栈图解:

561
来自专栏赵俊的Java专栏

删除链表中的元素

1022
来自专栏desperate633

LintCode 旋转链表题目分析代码

样例 给出链表1->2->3->4->5->null和k=2 返回4->5->1->2->3->null

674
来自专栏尾尾部落

[剑指offer] 包含min函数的栈

用一个栈stack保存数据,用另外一个栈temp保存依次入栈最小的数 比如,stack中依次入栈 5, 3, 4, 10, 2, 12, 1, 8 则te...

833
来自专栏书山有路勤为径

链表划分

LeetCode 86.Partition List 已知链表头节点指针head与数值X,将所有小于x的节点放在大于或等于x的节点前,且保持这些节点的原来的相...

584

扫描关注云+社区