0155._min_stack.md

Navigation

• Navigation
• Links:
• Solution 1 每次push的是一个元组
• Solution 2 用辅助栈记录每一次push之后，栈中最小的值
• 总结

Links:

1. https://leetcode.com/problems/min-stack/
2. https://leetcode-cn.com/problems/min-stack/

Solution 1 每次push的是一个元组

每次push(当前值，当前最小值)

class MinStack:
    def __init__(self):
        self.stack = [(None, float('inf'))]

    def push(self, x):
        self.stack.append((x, min(x, self.stack[-1][1])))
    
    def pop(self):
        if len(self.stack) > 1:
            self.stack.pop()[0]
    
    def top(self):
        return self.stack[-1][0]

    def getMin(self):
        return self.stack[-1][1]

---

class MinStack:
    def __init__(self):
        self.stack = []

    def push(self, x):
        if not self.stack:
            self.stack.append((x, x))
        else:
            self.stack.append((x, min(x, self.stack[-1][1])))

    def pop(self):
        if self.stack:
            self.stack.pop()[0]

    def top(self):
        if self.stack:
            return self.stack[-1][0]

    def getMin(self):
        if self.stack:
            return self.stack[-1][1]

---

Go

package main

import "math"

type Node struct {
	val int
	min int
}

type MinStack struct {
	s []*Node
}

func Constructor() MinStack {
	initNode := &Node{val: 0, min: math.MaxInt64}

	return MinStack{
		s: []*Node{initNode},
	}
}

func (this *MinStack) Push(val int) {
	m := this.s[len(this.s)-1].min
	m = min(m, val)
	node := &Node{val: val, min: m}
	this.s = append(this.s, node)
}

func (this *MinStack) Pop() {
	this.s = this.s[:len(this.s)-1]
}

func (this *MinStack) Top() int {
	return this.s[len(this.s)-1].val
}

func (this *MinStack) GetMin() int {
	return this.s[len(this.s)-1].min
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

Solution 2 用辅助栈记录每一次push之后，栈中最小的值

class MinStack:
    def __init__(self):
        self.data = []
        self.helper = []

    def push(self, x):
        self.data.append(x)
        if not self.helper or x <= self.helper[-1]:
            self.helper.append(x)
        else:
            self.helper.append(self.helper[-1])

    def pop(self):
        if self.data:
            self.helper.pop()
            return self.data.pop()

    def top(self):
        if self.data:
            return self.data[-1]

    def getMin(self):
        if self.helper:
            return self.helper[-1]

---

Go

package main

import "math"

type MinStack struct {
	stack    []int
	minStack []int
}

func Constructor() MinStack {
	return MinStack{
		stack:    []int{},
		minStack: []int{math.MaxInt64},
	}
}

func (this *MinStack) Push(val int) {
	this.stack = append(this.stack, val)
	top := this.minStack[len(this.minStack)-1]
	this.minStack = append(this.minStack, min(val, top))
}

func (this *MinStack) Pop() {
	this.stack = this.stack[:len(this.stack)-1]
	this.minStack = this.minStack[:len(this.minStack)-1]
}

func (this *MinStack) Top() int {
	return this.stack[len(this.stack)-1]
}

func (this *MinStack) GetMin() int {
	return this.minStack[len(this.minStack)-1]
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

总结

Solution 1 和 Solution 2思想一样。都是每次push的时候，存当前最小值。 Solution 1把最小值存在元组里，而Solution 2存在辅助栈里。