如何进行包含函数的栈分析

发布时间：2021-12-09 16:41:19 作者：柒染
来源：亿速云阅读：153

本篇文章为大家展示了如何进行包含函数的栈分析，内容简明扼要并且容易理解，绝对能使你眼前一亮，通过这篇文章的详细介绍希望你能有所收获。

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.min(); --> 返回 -3.

minStack.pop();

minStack.top(); --> 返回 0.

minStack.min(); --> 返回 -2.

提示：

各函数的调用总次数不超过 20000 次

解题思路：

1，注意本题是栈，需要和队列那个区分开

2，维护一个最小值栈

3，push 如果当前元素比最小值栈顶元素小，则放弃，否则插入

4，pop 如果栈顶元素和最小值栈顶元素相等，则同时出栈

5，注意细节，元素和最小值栈顶元素相等也要入栈

复习下队列那个题目

1，需要维护一个最小值双端队列

2，每次入队的时候从后往前找，找到比插入元素小（大）的元素，舍弃队列后面元素，将当前元素插入

代码实现

type MinStack struct {  data []int  minData []int}

/** initialize your data structure here. */func Constructor() MinStack {   return MinStack{}}

func (this *MinStack) Push(x int)  {   this.data=append(this.data,x)    if len(this.data)==1{        this.minData=append(this.minData,x)        return    }        l:=len(this.minData)    if x<=this.minData[l-1]{        this.minData=append(this.minData,x)    }    }

func (this *MinStack) Pop()  {    if len(this.data)==0{        return     }    l:=len(this.data)    v:=this.data[l-1]    this.data=this.data[:l-1:l-1]    l1:=len(this.minData)    if v==this.minData[l1-1]{        this.minData=this.minData[:l1-1:l1-1]    }    return}

func (this *MinStack) Top() int {     if len(this.data)==0{         return -1     }      return this.data[len(this.data)-1]}

func (this *MinStack) Min() int {        if len(this.data)==0{         return -1     }      return this.minData[len(this.minData)-1]}

/** * Your MinStack object will be instantiated and called as such: * obj := Constructor(); * obj.Push(x); * obj.Pop(); * param_3 := obj.Top(); * param_4 := obj.Min(); */

上述内容就是如何进行包含函数的栈分析，你们学到知识或技能了吗？如果还想学到更多技能或者丰富自己的知识储备，欢迎关注亿速云行业资讯频道。

如何进行包含函数的栈分析

相关阅读