(初级)8.最小栈

one_zheng · · 857 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。

  • push(x) -- 将元素 x 推入栈中。
  • pop() -- 删除栈顶的元素。
  • top() -- 获取栈顶元素。
  • getMin() -- 检索栈中的最小元素。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

使用两个栈来实现,一个栈来按顺序存储push进来的数据,另一个用来存出现过的最小值。

golang代码如下:

package stack

import (
    "container/list"
)

type Stack struct {
    list *list.List
}

func NewStack() *Stack {
    list := list.New()
    return &Stack{list}
}

func (stack *Stack) Push(value interface{}) {
    stack.list.PushBack(value)
}

func (stack *Stack) Pop() interface{} {
    e := stack.list.Back()
    if e != nil {
        stack.list.Remove(e)
        return e.Value
    }
    return nil
}

func (stack *Stack) Peak() interface{} {
    e := stack.list.Back()
    if e != nil {
        return e.Value
    }

    return nil
}

func (stack *Stack) Len() int {
    return stack.list.Len()
}

func (stack *Stack) Empty() bool {
    return stack.list.Len() == 0
}

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


type MinStack struct {
    s1, s2 *Stack
}

/** initialize your data structure here. */
func Constructor() MinStack {
    return MinStack{
        s1: NewStack(),
        s2: NewStack(),
    }
}

func (this *MinStack) Push(x int) {
    this.s1.Push(x)
    if this.s2.Empty() || x <= this.s2.Peak().(int) {
        this.s2.Push(x)
    }
}

func (this *MinStack) Pop() {
    x := this.s1.Pop()
    if x == this.s2.Peak().(int) {
        this.s2.Pop()
    }

}

func (this *MinStack) Top() int {
    return this.s1.Peak().(int)

}

func (this *MinStack) GetMin() int {
    return this.s2.Peak().(int)

}



有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:one_zheng

查看原文:(初级)8.最小栈

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

857 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传