本篇文章为大家展示了如何进行包含函数的栈分析,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。
定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 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();
*/
上述内容就是如何进行包含函数的栈分析,你们学到知识或技能了吗?如果还想学到更多技能或者丰富自己的知识储备,欢迎关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。