剑指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 条评论
登录 后参与评论

相关文章

来自专栏张俊红

数据结构-栈和队列

我们把类似于弹夹那种先进后出的数据结构称为栈,栈是限定仅在表尾进行插入和删除操作的线性表,我们把允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的...

942
来自专栏武培轩的专栏

快手2018春招后端笔试题解

计算(x^y)%N 题目描述 计算(x^y)%N 注:(x^y)表示x的y次方 输入描述: 每个测试用例一行 每行为空格隔开的 int64_t 类型,分别对应x...

3485
来自专栏老马说编程

(46) 剖析PriorityQueue / 计算机程序的思维逻辑

上节介绍了堆的基本概念和算法,本节我们来探讨堆在Java中的具体实现类 - PriorityQueue。 我们先从基本概念谈起,然后介绍其用法,接着分析实现代码...

1927
来自专栏来自地球男人的部落格

[LeetCode] 113. Path Sum II

【原题】 Given a binary tree and a sum, find all root-to-leaf paths where each pa...

1937
来自专栏博岩Java大讲堂

Java集合--Queue(Java中实现1)

3304
来自专栏F_Alex

数据结构与算法(四)-线性表之循环链表

前言:前面几篇介绍了线性表的顺序和链式存储结构,其中链式存储结构为单向链表(即一个方向的有限长度、不循环的链表),对于单链表,由于每个节点只存储了向后的指针,到...

1083
来自专栏coding for love

JS常用方法整理-遍历对象

JS中经常需要对对象的属性进行遍历,下面我们来总结一下JS遍历对象属性的几种方法。

492
来自专栏Flutter入门

Kotlin中的函数

函数还可以用中缀表示法调用,当他们是成员函数或扩展函数,只有一个参数,用 infix关键字标注

1034
来自专栏从流域到海域

二叉树的性质和常用操作代码集合

二叉树的性质和常用操作代码集合 性质: 二叉树的性质和常用代码操作集合 性质1:在二叉树的第i层上至多有2^i-1个结点 性质2:...

1959
来自专栏有趣的Python

玩转算法面试:(四)LeetCode查找类问题

查找问题 两类查找问题 查找有无:元素’a’是否存在?set;集合 查找对应关系(键值对应):元素’a’出现了几次?map;字典 通常语言的标准库中都内置set...

3226

扫码关注云+社区