Leetcode - Min Stack
https://leetcode.com/problems/min-stack/
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
- push(x) -- Push element x onto stack.
- pop() -- Removes the element on top of the stack.
- top() -- Get the top element.
- getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | type MinStack struct { minElement int arr []int}/** initialize your data structure here. */func Constructor() MinStack { return MinStack{ arr: []int{}, }}func (this *MinStack) Push(x int) { if len(this.arr) == 0 { this.arr = append(this.arr, x) this.minElement = x return } if x >= this.minElement { this.arr = append(this.arr, x) return } this.arr = append(this.arr, 2*x - this.minElement) this.minElement = x}func (this *MinStack) Pop() { if this.arr[len(this.arr)-1] > this.minElement { this.arr = this.arr[:len(this.arr)-1] return } y := this.arr[len(this.arr)-1] this.minElement = 2*this.minElement - y this.arr = this.arr[:len(this.arr)-1]}func (this *MinStack) Top() int { y := this.arr[len(this.arr)-1] if y > this.minElement { return y } minElement := 2*this.minElement - y return (y+minElement)/2}func (this *MinStack) GetMin() int { return this.minElement}/** * 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(); */ |
评论 (0)
