Aside: today is September 21, 2021. On the occasion of the Mid Autumn Festival, I wish you a happy holiday and a happy family!
Today, I want to summarize how to quickly master the algorithm in Leecode. PS today, I stroked the algorithm topics in Leecode, with a total of about 2050 questions. How to quickly understand the above topics in a limited time, I think in addition to more practice and practice, I should also be good at summarizing and classifying from so many topics to form a system. Only in this way can we do it with ease. To show others your code unhurried
Most of the questions in the question bank focus on Algorithms (time complexity, search, sorting and graph) and data structures (array, heap, queue, stack, tree and graph, set, hash and mapping). Later, if you brush the array related, you know it is a data structure. It is recommended that you focus on simple and medium, and you can pass the requirements of most companies and relevant posts.

You can sort and brush in the order of array and stack in the data structure.
Today, let's look at the * * "minimum stack" * * of heap, stack and queue.
Title Description: design a stack that supports push, pop and top operations and can retrieve the smallest element in a constant time.
push(x) -- pushes element x onto the stack.
pop() -- delete the element at the top of the stack.
top() -- get the stack top element.
getMin() -- retrieves the smallest element in the stack.
Example:

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.

Tips:
pop, top, and getMin operations are always called on non empty stacks.
Problem solving ideas (connect tuples to the stack)
The problem requires to obtain the minimum value in the stack in a constant time, so you can't calculate the minimum value when getMin(). It's best to calculate the minimum value in the current stack when push ing or pop.

The solution of this topic basically talks about the concept of "auxiliary stack", which is a common idea, but is there a more understandable method?

You can use a stack, which saves the value of each number x when it enters the stack and the minimum value in the stack after inserting the value. That is, each time a new element X is put into the stack, a tuple is saved: (the current value x, the minimum value in the stack).

This tuple is a whole, both in and out of the stack. That is, the top of the stack has both the value and the minimum value in the stack. The top() function obtains the current value of the top of the stack, that is, the first value of the top tuple; getMin() function is to obtain the minimum value in the stack, that is, the second value of the tuple at the top of the stack; pop() function deletes the tuple at the top of the stack.

Each time a new element is put into the stack, a new minimum value in the stack is required: compare the size of the currently newly inserted element x with the current minimum value in the stack (that is, the second value of the top tuple of the stack).

New element stack: when the stack is empty, save tuples (x, x); When the stack is not empty, save the tuple (x, min (the previous minimum value in the stack, x)))
Out of stack: delete the tuple at the top of the stack.
The code is as follows:

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        if not self.stack:
            self.stack.append((x, x))
        else:
            self.stack.append((x, min(x, self.stack[-1][1])))
        

    def pop(self):
        """
        :rtype: void
        """
        self.stack.pop()
        

    def top(self):
        """
        :rtype: int
        """
        return self.stack[-1][0]
        

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


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

2, The kth largest element in the array
Title Description: given the integer array nums and integer k, please return the K largest element in the array.

Note that you need to find the K largest element after the array is sorted, not the k different element.

Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Tips:
1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104
Problem solving ideas:
This question must be understood and remembered, because it is a high-frequency topic.

This question can be referred to Simple python template for all TopK problems based on fast scheduling