I tried LeetCode every day 155. Min Stack (Python, Go)

What is Leetcode

leetcode.com This is the practice of coding interviews for software developers. A total of more than 1,500 coding questions have been posted, and it seems that the same questions are often asked in actual interviews.

Introduction to golang + algorithm I will solve it with go and Python to strengthen the brain. (Python is weak but experienced)

35th question (problem 155)

155. Min Stack

the issue's details

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.

Japanese translation

Design a stack that supports push, pop, top, and minimum element capture over time.

--push (x)-Push element x onto the stack. --pop ()-Removes the top element of the stack. --top ()-Get the top element. --getMin ()-Get the smallest element in the stack.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Way of thinking

1. Read the problem statement to understand the ideal return value and array processing
2. You need to keep the number you have saved and the smallest number you have saved.
3. Implement pop or push while keeping that number first and the smallest number second.

Answer code

class MinStack:

    def __init__(self):
        self.q = []

    # @param x, an integer
    # @return an integer
    def push(self, x):
        curMin = self.getMin()
        if curMin == None or x < curMin:
            curMin = x
        self.q.append((x, curMin));

    # @return nothing
    def pop(self):
        self.q.pop()


    # @return an integer
    def top(self):
        if len(self.q) == 0:
            return None
        else:
            return self.q[len(self.q) - 1][0]


    # @return an integer
    def getMin(self):
        if len(self.q) == 0:
            return None
        else:
            return self.q[len(self.q) - 1][1]

--I'll write it in Go too!

type MinStack struct {
	vals [][]int
}

/** initialize your data structure here. */
func Constructor() MinStack {
	return MinStack{vals: [][]int{}}
}

func (this *MinStack) Push(x int) {
	if len(this.vals) == 0 {
		this.vals = [][]int{{x, x}}
	} else {
		this.vals = append(this.vals, []int{x, min(x, this.GetMin())})
	}
}

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

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

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

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