C# Solution with 2 Stacks with comments to be easy for understanding


  • 0
    K
    public class MaxStack  {
    
    /** initialize your data structure here. */
    int max = int.MinValue;
    Stack<int> st;
    Stack<int> temp;
    
    public MaxStack() {
        st = new Stack<int>();
        temp = new Stack<int>();
    }
    
    public void Push(int x) {
        max = Math.Max(max , x);
        st.Push(x);
    }
    
    public int Pop() {
        
        // Pop and recalculate the max
        int elm = st.Pop();
        
        max = int.MinValue;
    
        while(st.Count > 0){
    
            int x = st.Pop();
            max = Math.Max(x , max);
            temp.Push(x);
        }
    
        while(temp.Count > 0) {
    
            st.Push(temp.Pop());
    
        }
        
        return elm;
        
    }
    
    public int Top() {
        return st.Peek();
    }
    
    public int PeekMax() {
         return max;
    }
    
    public int PopMax() {
        
        int currentMax = int.MinValue;
        
        // Reset the value of the max to MinValue
        if(st.Count == 1) { max = int.MinValue; return st.Pop(); }
        
        bool found = false;
        
        while(st.Count > 0){
            int elm = st.Pop();
            
            currentMax = Math.Max(currentMax , elm);
            // in case the max was duplicated in the stack , just remove it once!
            if(elm == max && !found){
                found = true;
                continue;
            }
            
            temp.Push(elm);
        }
        
        // set max to MinValue again to be able to recalculate the max!
        max = int.MinValue;
        
        if(temp.Count > 0) {
         
            while(temp.Count > 0){
    
                int elm = temp.Pop();
                max = Math.Max(elm , max);
                st.Push(elm);
            }
        }
           
        return currentMax;
       }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.