Design a stack with getmin function

Design one with getMin Stack of functions

【 subject 】

​ Implement a special stack , On the basis of realizing the basic functions of stack , The operation of the smallest element in the return stack .

【 requirement 】

​ 1.pop、push、getMin The time complexity of operation is O（1）.

​ 2. The designed stack type can use the existing stack structure .

【 Ideas 】

​ Use two stacks , A stack a Normal access , Another stack b Used to maintain the minimum value , Always keep b The top of the stack is the current a The minimum value in the stack .

​ Method 1 【 The depth of the two stacks is inconsistent 】： When entering the stack , Each entry a When the stack , If b The stack is empty. , Enter into a The stack enters at the same time b Stack , If you enter a Stack value ratio b The top of the stack is big , No entry , conversely , Get into b Stack , Update minimum ; Out of the stack , If the stack value is equal to b To the top of the stack , Just put b At the top of the stack , Update minimum , conversely ,b Stack does not update .

give an example ： Press in in turn 3、4、5、1、2、1 In the process of ,stackData（a） and stackMin（b） The changes are shown in the figure below .

explain ： The picture comes from Zuoshen's program code interview guide , For learning purposes only .

​ Method 2 【 The two stacks have the same depth 】： When entering the stack , Get into a Stack time , If b The stack is empty. , Get into b Stack , If b Stack is not empty and b Stack top less than a Stack new stack value , Then put the b The top of the stack is pushed again b Stack , The height is consistent ; Out of the stack , Both stacks pop up at the same time .

give an example ： Press in in turn 3、4、5、1、2、1 In the process of ,stackData（a） and stackMin（b） The changes are shown in the figure below .

【 Code 】

【Java】

Method 1 ：

package keafmd.accumulate.codeinterviewguide.stackwithgetmin;import java.util.Stack;/** * Keafmd * * @ClassName: getMinStack * @Description:  Stack with minimum value  * @author:  Cowherd Conan  * @date: 2022-06-20 14:29 */public class MyStack1 {    private Stack<Integer> stacka;    private Stack<Integer> stackb;    public MyStack1(){        stacka = new Stack<>();        stackb = new Stack<>();    }    // Push     public void push(Integer val){        stacka.push(val);        if(stackb.isEmpty()||val<=getMin()){            stackb.push(val);        }    }    // Out of the stack     public Integer pop(){        if(stacka.isEmpty()){            throw new RuntimeException("Stack is empty!");        }        Integer val = stacka.pop();        if(val.equals(getMin())){            stackb.pop();        }        return val;    }    // Get the minimum     public Integer getMin(){        if(stackb.isEmpty()){            throw new RuntimeException("Stack is empty!");        }        return stackb.peek();    }}

Method 2 ：

package keafmd.accumulate.codeinterviewguide.stackwithgetmin;import java.util.Stack;/** * Keafmd * * @ClassName: MyStack2 * @Description:  Stack with minimum value  * @author:  Cowherd Conan  * @date: 2022-06-20 15:07 */public class MyStack2 {    private Stack<Integer> stacka;    private Stack<Integer> stackb;    public MyStack2(){        stacka = new Stack<>();        stackb = new Stack<>();    }    // Push     public void push(Integer val){        stacka.push(val);        if(stacka.isEmpty()||val<getMin()){            stackb.push(val);        }else{            stackb.push(getMin());        }    }    // Out of the stack     public Integer pop(){        if(stacka.isEmpty()){            throw new RuntimeException("Stack is empty!");        }        Integer val = stacka.pop();        stackb.pop();        return val;    }    // Get the minimum     public Integer getMin(){        if(stackb.isEmpty()){            throw new RuntimeException("Stack is empty!");        }        return stackb.peek();    }}

【 summary 】

Method one and method two actually use stackb The stack holds stacka The minimum value of each step . The common point is that the time complexity of all operations is O（1）、 The complexity of space is O（n）. The difference is that ： In method one stackb Save space when pressing , But the pop-up operation takes a little time ; Method 2 stackb It takes a little space to press in , But the pop-up operation saves a little time .