Implementation and Optimization of minimum Stack

Minimum stack

Implement a minimum stack, optimizing step by step, from extra space O (N) to O (1). The interviewer values code logic. Push,pop,top,getMin is all O (1) time.

1 use a minimum stack to store the minimum value 1.1 points:

2 stacks, data to store data and minValue to store minimum values.

When push, data directly push data; minValue puts directly into the current minimum value. There is an optimization for minValue, when the data of push is larger than the current minimum value, we can not insert the minimum value of minValue; if it is less than or equal to the minimum value, we need to put the latest minimum value push into the stack minValue.

When pop, data directly pop the data; at the same time, update minValue, and the updated policy is the number of pop corresponding to the optimization in push. If = = the current minimum value, you need to pop the minValue once.

GetMin: just return the top element of the stack minValue directly.

Top: just return the top element of the stack data directly.

1.2 complexity and code

Extra space consumption O (N), how to optimize to O (1).

Public class MinStack1 {private Stack data = new Stack (); private Stack minValue = new Stack (); public void push (int x) {data.push (x); if (minValue.isEmpty () | | x 0? Top + minValue: minValue;} public int getMin () {return minValue;}}

New channel IELTS