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

相关文章

来自专栏java学习

面试题53(考察求职者对String声明变量在jvm中的存储方法)

(单选题) 1、有如下一段代码,请选择其运行结果() public class StringDemo{ private static final Stri...

2803
来自专栏Java帮帮-微信公众号-技术文章全总结

13(01)总结StringBuffer,StringBuilder,数组高级,Arrays,Integer,Character

1:StringBuffer(掌握) (1)用字符串做拼接,比较耗时并且也耗内存,而这种拼接操作又是比较常见的,为了解决这个问题,Java就提供了 一...

3795
来自专栏赵俊的Java专栏

两个字符串是变位词

1033
来自专栏从零开始学 Web 前端

06 - JavaSE之常用类

public StringBuffer append(...) 可以为该 StringBuffer 对象添加字符序列,返回添加后的该 StringBuffer ...

652
来自专栏郭耀华‘s Blog

Java集合框架(四)—— Queue、LinkedList、PriorityQueue

Queue接口   Queue用于模拟了队列这种数据结构,队列通常是指“先进先出”(FIFO)的容器。队列的头部保存在队列中时间最长的元素,队列的尾部保存...

3226
来自专栏机器学习入门

LWC 53:693. Binary Number with Alternating Bits

LWC 53:693. Binary Number with Alternating Bits 传送门:693. Binary Number with Alte...

2218
来自专栏老马说编程

(89) 正则表达式 (中) / 计算机程序的思维逻辑

上节介绍了正则表达式的语法,本节介绍相关的Java API。 正则表达式相关的类位于包java.util.regex下,有两个主要的类,一个是Pattern,另...

1907
来自专栏nnngu

数据结构05 栈

这篇文章要总结的是栈,主要从以下几个方面来进行总结。 1、栈是什么 2、栈的存储结构 3、栈的常见操作及代码实现 1、栈是什么 栈是一种特殊的线性表,它限定了只...

3486
来自专栏无题

链式存储线性表(LinkedList)数据结构解析

LinkedList内部是通过链表来实现的 一、节点分析 LinkedList内部是通过链表来实现的,那么就少不了节点,所以在源码中必然能找到这样一个节点。 ...

3236
来自专栏武培轩的专栏

剑指Offer-栈的压入、弹出序列

题目描述 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压...

3267

扫码关注云+社区