9.27最小栈设计 - WisperDin/blog GitHub Wiki

描述

设计一个支持 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.

思路

可以通过两个栈来实现这个逻辑，一个栈是正常存数据的栈data，另外一个栈是存最小值的栈minValue

• Push 往data栈push，如果minValue栈为空或者当前要Push的值比栈顶的值更小，向minValue栈push；否则直接返回
• Pop data栈pop出栈顶，考察pop出的元素是否与minValue中的栈顶元素相同，相同则pop出minValue栈顶元素
• GetMin 获取minValue栈顶元素
• Top 获取data栈顶元素

实现

package MinStack

import "fmt"

type MinStack struct {
	minValue *Stack
	data *Stack
}

func NewMinStack() *MinStack {
	return &MinStack{
		minValue:&Stack{},
		data:&Stack{},
	}
}


func (this *MinStack) Push(x int)  {
	this.data.Push(x)
	minValue,haveVal := this.minValue.Top()
	if !haveVal || x<minValue {
		this.minValue.Push(x)
	}
	return
}


func (this *MinStack) Pop()  {
	popVal,success := this.data.Pop()
	if !success {
		return
	}
	minValue,haveVal := this.minValue.Top()
	if !haveVal {
		fmt.Println("Pop minValue top no value!")
		return
	}
	if popVal != minValue {
		return
	}
	this.minValue.Pop()
}


func (this *MinStack) Top() int {
	topVal,haveVal := this.data.Top()
	if !haveVal {
		return -1
	}
	return topVal
}


func (this *MinStack) GetMin() int {
	minValue,haveVal := this.minValue.Top()
	if !haveVal {
		return -1
	}
	return minValue
}