剑指Offer(二十):包含min函数的栈

  • A+
所属分类:剑指Offer
摘要

定义栈的数据结构,请在类型中实现一个能够得到栈最小元素的min函数。

剑指Offer(二十):包含min函数的栈

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

定义的数据结构,请在类型中实现一个能够得到最小元素的min函数。

1、思路

使用两个stack,一个为数据栈,另一个为辅助栈。数据栈用于存储所有数据,辅助栈用于存储最小值。

举个例子:

入栈的时候:首先往空的数据栈里压入数字3,显然现在3是最小值,我们也把最小值压入辅助栈。接下来往数据栈里压入数字4。由于4大于之前的最小值,因此我们只要入数据栈,不压入辅助栈。

出栈的时候:当数据栈和辅助栈的栈顶元素相同的时候,辅助栈的栈顶元素出栈。否则,数据栈的栈顶元素出栈。

获得栈顶元素的时候:直接返回数据栈的栈顶元素。

栈最小元素:直接返回辅助栈的栈顶元素。

2、代码

C++:

Jack Cui
阿里云ECS

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: