剑指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帮帮-微信公众号-技术文章全总结

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

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

4225
来自专栏个人随笔

房上的猫:StringBuffer类

一.使用StringBuffer类  StringBuffer类位于java.lang包中,是String类的增强类  步骤:   1.声明StringBuff...

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

C++抛出异常与传递参数的区别

C++的异常处理机制有3部分组成:try(检查),throw(抛出),catch(捕获)。把需要检查的语句放在try模块中,检查语句发生错误,throw抛出异常...

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

06 - JavaSE之常用类

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

792
来自专栏老马说编程

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

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

1977
来自专栏java学习

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

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

3013
来自专栏无题

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

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

3326
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题22栈的压入、弹出序列

本题的详细分析过程均在代码的注释中: import java.util.Stack; /** * 题目:输入两个整数序列,第一个序列表示栈的压入顺序,请判断...

3037
来自专栏赵俊的Java专栏

两个字符串是变位词

1523
来自专栏AILearning

字符串的学习

1> “==”与“equals”的区别 “==”判断的是两个字符串对象在内存中的首地址,就是判断是否是同一个字符串对象; 而equals()判断的是两个字符串对...

2005

扫码关注云+社区

领取腾讯云代金券