golang刷leetcode 技巧（32）包含min函数的栈

golang算法架构leetcode技术php 2020-03-15

106

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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();
 */

golang

文章转载自golang算法架构leetcode技术php，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

golang刷leetcode 技巧（32）包含min函数的栈

评论