算法:最小栈
13122256420
659
2024-02-26

设计一个支持 push,pop,top操作的栈

js版本
function minStack() {
    class MinStack {
        constructor() {
            this.stack = [];
            this.min_stack = []
        }

        push(x) {
            this.stack.push(x)
            if (this.min_stack.length === 0 || x <= this.min_stack[this.min_stack.length - 1]) {
                this.min_stack.push(x)
            }
        }

        pop() {
            if (this.stack.length === 0) return
            if (this.stack.pop() === this.min_stack[this.min_stack.length - 1]) {
                this.min_stack = this.min_stack.pop()
            }
        }
    }

    let m = new MinStack()
    m.push(10)
    m.push(20)
    m.push(30)
    m.push(50)
    m.pop()
    m.pop()

    console.log(m.stack,m.min_stack)
}
minStack()
go版本
type MinStack struct {
	stack     []int
	min_stack []int
}

func (t *MinStack) New() MinStack {
	return MinStack{
		stack:     nil,
		min_stack: nil,
	}
}

func (t *MinStack) push(x int) {
	t.stack = append(t.stack, x)
	if t.min_stack == nil || x <= t.min_stack[len(t.min_stack)-1] {
		t.min_stack = append(t.min_stack, x)
	}
}

func (t *MinStack) pop() {
	if t.stack == nil {
		return
	}
	a := t.stack[len(t.stack)-1:]
	t.stack = t.stack[:len(t.stack)-1]
	fmt.Println(a[0], t.min_stack[len(t.min_stack)-1], "=======")
	if a[0] == t.min_stack[len(t.min_stack)-1] {
		t.min_stack = t.min_stack[:len(t.min_stack)-1]
	}
}

func (t *MinStack) top() int {
	return t.stack[len(t.stack)-1]
}
func minStack() {
	var m = MinStack{}
	min := m.New()
	min.push(10)
	min.push(10)
	min.push(101)
	min.push(101)
	min.pop()
	min.pop()

	fmt.Println(min.stack, min.min_stack, min.top())
}
rust版本
fn minStack() {
    struct MinStack {
        stack: Vec<i32>,
        min_stack: Vec<i32>,
    }

    impl MinStack {
        fn new() -> Self {
            MinStack {
                stack: Vec::new(),
                min_stack: Vec::new(),
            }
        }
        fn push(&mut self, x: i32) {
            self.stack.push(x);
            if self.min_stack.is_empty() || x <= *self.min_stack.last().unwrap() {
                self.min_stack.push(x);
            }
        }
        fn pop(&mut self) {
            if self.stack.is_empty() { return; }
            if self.stack.pop().unwrap() == *self.min_stack.last().unwrap() {
                self.min_stack.pop();
            }
        }
        fn top(&self) -> i32 {
            *self.stack.last().unwrap()
        }
        fn get_min(&self) -> i32 {
            *self.min_stack.last().unwrap()
        }
    }

    let mut m = MinStack::new();

    m.push(100);
    m.push(101);
    m.push(102);

    println!("{:?} === {:?}", m.stack,m.min_stack);
    println!("{:?}", m.top());
    println!("{:?}", m.get_min());
}