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

How to find the minimum value of real-time sequence in O (1)? aiming at this problem, this article introduces the corresponding analysis and solution in detail, hoping to help more partners who want to solve this problem to find a more simple and feasible method.

Minimum stack

The minimum stack can find the minimum value of the sequence in the stack in O (1), so this feature is often used to improve the performance of the algorithm. Let's take a look at one implementation of it.

Analysis process

Stack analysis:

Push the element to the mainstack, and only if the current element is smaller than the element at the top of the tmpstack stack (actually stored as the element index in mainstack), it is the index that goes into the stack.

Assuming that there are currently n elements in mainstack, there are at most n elements in tmpstack. When it is equal to n, it indicates that the original stack order is a monotone decreasing sequence.

Out-stack analysis:

Elements are removed from the mainstack, but pay attention to whether the index of the stack element is equal to the top of the tmpstack stack, if you need to unstack the top element of the tmpstack stack. Predictably, the top-of-stack index must be less than or equal to the index of the outgoing stack element (within the mainstack stack).

Two points should be paid attention to in this question:

The element index of the main stack is pushed in the temporary stack.

If the temporary stack is empty in push, you need to push this element into the main stack index first.

Code class MinStack (object): def _ _ init__ (self): "initialize your data structure here." Self.mainstack= [] self.tmpstack = []

Push into the element:

Def push (self, val): ": typeval: int: rtype: None"self.mainstack.append (val) if not self.tmpstack: self.tmpstack.append (len (self.mainstack)-1) # smaller than top of tmpstack if self.mainstack [self.tmpstack [- 1]] > val: self.tmpstack.append (len (self.mainstack)-1)

Off-stack element:

Def pop (self): ": rtype: None"# min val of tmpstack equals top of mainstack if self.tmpstack and self.tmpstack [- 1] = len (self.mainstack)-1: self.tmpstack.pop () return self.mainstack.pop () def top (self):": rtype: int "" if self.mainstack: return self.mainstack [- 1]

Using tmpstack auxiliary stack, the minimum query complexity of O (1) is obtained.

Def getMin (self): ": rtype: int"if self.tmpstack: return self.mainstack [self.tmpstack [- 1]] this is the answer to the question about how to find the minimum value of a real-time sequence in O (1). I hope the above content can be of some help to you, if you still have a lot of doubts to solve. You can follow the industry information channel for more related knowledge.

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.