Shulou(Shulou.com)06/01 Report--

This article is about how LeetCode implements a stack that contains min functions. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

Topic description

To define the data structure of the stack, implement a min function in this type that can get the smallest elements of the stack. In this stack, the time complexity of calling min, push, and pop is O (1).

The total number of calls to each function does not exceed 20000

Sample topic MinStack minStack = new MinStack ()

MinStack.push (- 2)

MinStack.push (0)

MinStack.push (- 3)

MinStack.min ();-- > returns-3.

MinStack.pop ()

MinStack.top ();-- > returns 0.

MinStack.min ();-- > returns-2.

Question: what data structure is needed internally to satisfy that all operations are O (1)? is one stack enough? If the solution is to make the complexity of push and pop O (1), the traditional stack can handle it. The difficulty is how to make the min function also O (1). If we can always maintain the minimum value of all the elements, then the min function can return it directly, but the problem is that it is possible to get the minimum value of pop in the case of pop, and how to get the minimum value after pop (that is, the original second minimum value)? It is obvious that one variable is not enough to store multiple minimum values. According to the analysis in the previous step, we can consider introducing an additional monotonous decreasing stack, with the current minimum at the top of the stack, followed by the second smallest and the third smallest. In this way, if pop has a minimum value, the top of the monotonous stack will still keep the minimum value after pop. Every time min only needs to take the top of the stack, and when push also needs additional operations, because it is a monotonous stack, it only needs to push to the monotonous stack when the new value is less than or equal to the top of the stack. Pay special attention to push to the monotonous stack when it is equal to the top of the stack, because if it is not push for the repeated minimum value x, then after one of the subsequent pop, the top of the stack (no longer x) is inconsistent with the actual minimum value (still x). Complexity time complexity O (1) various operations are constant complexity space complexity O (N) uses two stack codes class MinStack:

Def _ init__ (self):

"

Initialize your data structure here.

"

# A normal stack and a monotonous decreasing stack

Self.minstack = []

Self.stack = []

Def push (self, x: int)-> None:

Self.stack.append (x)

If not self.minstack or x None:

If not self.stack:

Return

X = self.stack.pop ()

If x = = self.minstack [- 1]:

# if the top of the monotone stack happens to be equal to the value of pop, pop the monotone stack as well

Self.minstack.pop ()

Def top (self)-> int:

If not self.stack:

Return-1

Return self.stack [- 1]

Def min (self)-> int:

If not self.minstack:

Return-1

Return self.minstack [- 1]

Thank you for reading! This is the end of the article on "how LeetCode implements the stack containing min functions". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, you can share it out for more people to see!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.