Problem description

A stack with push and pop operations, whose time complexity is O(1).
The algorithm max operation is designed to find the maximum value in the stack. The time complexity of this operation is also required to be O(1).
The storage mode of stack, the operation of push and pop can be modified, but the time complexity of O(1) is not required

thinking

It's easy to think of declaring a maximum stack in addition to the original data stack. Each time the data is added, the latest maximum value is determined, and then the current maximum value is stored in maxStack. In addition to the original data pop(), for the elements in maxStack, first of all, we need to determine whether the top element in the original data stack is equal to the top element in maxStack. If it is equal, an element will pop up in maxStack. If it is not equal, we don't need to operate maxStack.

The spatial complexity of this method is O(n). The next article will introduce the method of O(1).

code

public class MaxStack {

    // Used to store raw data
    private Stack<Integer> primaryStack = new Stack<Integer>();

    // It is used to store the maximum value. Each time a new element is added, it is necessary to determine whether the current element is greater than the maximum value obtained after the last element is added
    private Stack<Integer> maxStack = new Stack<Integer>();

    //private int maxValue;

    public void push(int num) {
        primaryStack.push(num);
        if(maxStack.isEmpty()) {
            maxStack.push(num);
        }else{
            int maxValue = maxStack.peek();
            // The judgment here has a problem with space occupation
            // That is, the same maximum value may be stored repeatedly
            // For example, when the input element is 1 2 5 5 5
            // 1 2 5 5 5 stored in maxStack
            // In order to avoid repeated storage and save space, it is necessary to mark the repeated situation
            if(num>=maxValue){
                maxStack.push(num);
            }
        }
    }
    
    public int pop(){
        // If the original data stack is empty, the stack cannot be generated,
        if(primaryStack.isEmpty()) {
            // When the peek element in the Stack class is used here, if it is null, the exception is thrown
            // You can also return a number, which is used to identify the case when it is empty
            throw new EmptyStackException();
        }
        int maxValue = primaryStack.peek();
        if(maxValue == maxStack.peek()) {
            maxStack.pop();
        }
        return primaryStack.pop();
    }

    public int getMaxValue(){
        return maxStack.peek();
    }
}