[每日一道小算法（十四）] [栈] 包含min函数的栈（剑指offer习题）

Love The Way You Lie 2023-07-04 06:19 24阅读 0赞

前言：  
很晚了，才来更新，不说废话了，直接上题吧。  
2020/5/13 更新Go语言代码样例。

### 题目描述 ###

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

### 题目解析 ###

我们首先能象到在栈里添加一个成员变量存放最小的元素。每次压入一个新元素进栈的时候，如果钙元素比当前最小的元素还小，则更新最小元素。这么做，看上去是没问题。但是我们忽略一个问题，那就是如果当前栈中的最小元素被弹出了，如何得到下一个最小元素呢。所以这个方法不行的。所以就有了一个更好的方法。我们可以使用两个栈，一个栈作为辅助栈，一个栈作为存放数据的栈。每当有元素压入栈的时候，都会和辅助栈中的栈顶元素作比较，如果比栈顶元素小，则直接入栈顶，如果比这个栈顶元素大，则将现在这个栈顶元素再次放入栈顶。存放数据的栈弹出的时候，辅助栈也要弹出，保证元素长度一致性。好嘞，这个方法是可行的，那么开始写代码吧。

### 代码样例 ###

package com.asong.leetcode.minFunction;
    
    import java.util.Stack;
    
    public class Solution { 
    
        Stack<Integer> stackData = new Stack<Integer>();
        Stack<Integer> stackMin = new Stack<Integer>();
    
        public void push(int node) { 
            stackData.push(node);
            if(stackMin.empty())
            { 
                stackMin.push(node);
            }else { 
                if(node <= stackMin.peek())
                { 
                    stackMin.push(node);
                }else { 
                    stackMin.push(stackMin.peek());
                }
            }
        }
    
        public void pop() { 
            stackMin.pop();
            stackData.pop();
        }
    
        public int top() { 
            return stackData.peek();
        }
    
        public int min() { 
            return stackMin.peek();
        }
    }

/** * Your MinStack object will be instantiated and called as such: * obj := Constructor(); * obj.Push(x); * obj.Pop(); * param_3 := obj.Top(); * param_4 := obj.GetMin(); */
    type MinStack struct{ 
    	stack []int
    	minStack []int
    }
    
    func Constructor() MinStack{ 
    	return MinStack{ 
    		stack: []int{ },
    		minStack: []int{ math.MaxInt64},
    	}
    }
    
    func (this *MinStack) Push(x int){ 
    	this.stack = append(this.stack,x)
    	top := this.minStack[len(this.minStack)-1]
    	this.minStack = append(this.minStack,min(x,top))
    }
    
    func (this *MinStack) Pop(){ 
    	this.stack = this.stack[:len(this.stack)-1]
    	this.minStack = this.minStack[:len(this.minStack)-1]
    }
    
    func (this *MinStack) Top() int{ 
    	return this.stack[len(this.stack)-1]
    }
    
    func (this *MinStack) GetMin() int{ 
    	return this.minStack[len(this.minStack)-1]
    }
    
    func min(x,y int) int{ 
    	if x<y{ 
    		return x
    	}
    	return y
    }