一天一道算法题（27）：最小栈

155. 最小栈文章目录[155. 最小栈](https://leetcode.cn/problems/min-stack/)思路- 辅助栈- 不使用辅助栈使用变量记录最小值结语设计一个支持pushpoptop操作并能在常数时间内检索到最小元素的栈。实现MinStack类:MinStack()初始化堆栈对象。void push(int value)将元素value推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。示例 1:输入 [MinStack,push,push,push,getMin,pop,top,getMin] [[],[-2],[0],[-3],[],[],[],[]] 输出 [null,null,null,null,-3,null,0,-2] 解释 MinStack minStack new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); -- 返回 -3. minStack.pop(); minStack.top(); -- 返回 0. minStack.getMin(); -- 返回 -2.思路- 辅助栈既然我们要维护一个函数且这个函数要求在O(1)时间复杂度取出最小值那我们就有三个办法一个是维护最小栈一个是给栈排序一个是记录最小值这里我们直接pass给栈排序因为这违背了栈的定义且栈排序之后在取出顶部元素的时候会直接出错辅助栈就是最小栈栈顶维护最小值方便直接取出记录最小值是下一个方法时间复杂O(1)空间复杂度O(n)我们就不把返回长度的库函数当做O(n)这里也可以使用一个变量记录长度当入栈就出栈就–这样时间复杂度就是O(1)了代码演示typeMinStackstruct{//记录所有元素的栈val[]int//维护单调栈min[]int}funcConstructor()MinStack{//初始化分配内存minStack:MinStack{val:[]int{},min:[]int{},}returnminStack}func(this*MinStack)Push(valueint){//如果push进来元素我们应该直接入val栈this.valappend(this.val,value)//如果入栈的元素比最小值还要小那我们要入最小栈否则就不入栈//另外一种情况是如果最小栈里面为空那我们直接入栈iflen(this.min)0||valuethis.GetMin(){this.minappend(this.min,value)}}func(this*MinStack)Pop(){//删除val栈顶的元素的时候我们要考虑栈顶元素是不是等于最小栈栈顶的元素因为如果等于最小栈的栈顶元素我们此时要弹出两个栈顶的元素ifthis.val[len(this.val)-1]this.min[len(this.min)-1]{this.minthis.min[:len(this.min)-1]}this.valthis.val[:len(this.val)-1]}func(this*MinStack)Top()int{//直接返回val栈顶元素returnthis.val[len(this.val)-1]}func(this*MinStack)GetMin()int{//返回最小栈的栈顶元素returnthis.min[len(this.min)-1]}- 不使用辅助栈使用变量记录最小值我们可以使用min 变量记录最小值把每一次要入栈的元素与当前的元素做差如果差小于0那我们就更换否则就不更换如果弹出栈顶的元素我们判断当前栈顶元素与最小值的差如果等于0那我们就更新最小值这里需要O(n)时间复杂度依次遍历如果是返回最小值我们直接把该变量的值返回即可时间复杂度O(n)空间复杂度O(1)代码演示typeMinStackstruct{//入栈每一个元素valStack[]int//维护最小值minint}funcConstructor()MinStack{returnMinStack{valStack:[]int{},//初始化为int32的最大值min:math.MaxInt32,}}func(this*MinStack)Push(valueint){//比较如果新入栈的元素更小更换值ifvaluethis.GetMin(){this.minvalue}this.valStackappend(this.valStack,value)}func(this*MinStack)Pop(){//如果弹出的元素就等于最小值我们需要更新最小值时间复杂度为O(n)ifthis.Top()this.min{minTemp:math.MaxInt32//不遍历最后一位给长度-1fori:0;ithis.L()-1;i{ifthis.valStack[i]minTemp{minTempthis.valStack[i]}}//更新this.minminTemp}//弹出栈顶元素this.valStackthis.valStack[:this.L()-1]}func(this*MinStack)Top()int{returnthis.valStack[len(this.valStack)-1]}func(this*MinStack)GetMin()int{returnthis.min}func(this*MinStack)L()int{returnlen(this.valStack)}/** * Your MinStack object will be instantiated and called as such: * obj : Constructor(); * obj.Push(value); * obj.Pop(); * param_3 : obj.Top(); * param_4 : obj.GetMin(); */结语本文是 《算法题目解析系列》 的第 [27] 篇本系列将持续更新每篇都提供清晰的思路与编程语言实现。欢迎关注第一时间获取更新。如果你有想看的题目也可以在评论区留言告诉我。