我们今天的面试题是这样的……题目定义了栈的数据结构。请在此类型中实现一个min函数，该函数可以获取堆栈的最小元素。在这个栈中，调用min，push和pop的时间复杂度为O(1)。示例：MinStackminStack=newMinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.min();-->return-3.minStack.pop();minStack.top();-->return0.minStack.min();-->return-2。LeetCode地址：leetcode-cn.com/problems/ba...首先想到的是，这道题本身很容易理解，其实现的难点在于以下两个方面：栈的）操作，如果删除了当前的最小值，我们如何找到下一个最小值呢？保证调用min、push和pop的时间，复杂度为O(1)。也就是说，如果我们在执行pop的时候取出栈中的最小值，那么如何找到栈中下一个最小的元素呢？并且操作的时间复杂度必须保证为O(1)。这个时间复杂度限制了我们去掉最小值后通过遍历找到下一个最小值，所以这就成了这道题的难点。比如我们去掉下面这个top元素值时：因为最小值为1，所以去掉之后最小值也被去掉了，如下图：那么，让我们一起思考3分钟，想想应该怎么办be这个问题怎么处理~解题思路其实我们可以在每次入栈的时候判断当前元素是否小于最小值。是最小值，我们也可以通过获取下一个元素得到一个新的最小值，执行流程如下。操作步骤1将第一个元素压入栈中，因为是第一个元素，所以最小值就是这个元素的值。操作步骤2将第二个元素入栈，如下图所示：因为入栈的元素3小于8，所以先将栈中原来的最小值8入栈，然后再入栈3推入堆栈。操作步骤3将第三个元素压入栈中，如下图所示：由于压入的元素5大于3，所以栈中的最小值不变，直接将元素5压入栈中。Step4继续入栈，如下图：入栈元素1小于3，所以将原来的最小值3先入栈，再入栈1，最小的入栈栈中的值变为1。第五步：执行弹出操作，如下图：[Pictureuploading...(image-f68dcf-1602769401330-6)]元素1被弹出栈，判断当前元素为栈的最小值，于是将栈顶元素3设置为最小值，取出元素3，如下图：操作步骤6继续出栈，如下图所示：因为元素5不是当前最小值，所以直接出栈。Step7继续出栈，如下图：因为弹出的元素3是最小值，所以继续设置最小值为栈顶元素8，弹出栈顶元素，为如下图所示：这样，剩下的最后一个元素就没有了。最后一个元素出栈后，变成空栈，执行整个流程。实现代码1接下来，我们用代码实现上面的思路。我们使用数组实现的栈来实现相关功能。代码如下：classMinStack{privateint[]data;//栈数据privateintmaxSize;//最大长度privateinttop;//栈顶指针（下标）privateintmin;//最小值//构造函数publicMinStack(){//设置默认值valuemaxSize=10000;data=newint[maxSize];top=-1;min=Integer.MAX_VALUE;}//压入栈（添加元素）publicvoidpush(intx){if(min>=x){//遇到较小的值，记录原来的最小值（入栈）data[++top]=min;min=x;}//将当前值入栈data[++top]=x;}//入栈（取出栈顶元素）publicvoidpop(){if(min==data[top]){min=data[--top];//得到原来的最小值，并且（把原来的最小值)出栈}--top;//弹出栈}//查找栈顶元素publicinttop(){returndata[top];}//查询最小值publicintmin(){returnmin;}}上面代码在LeetCode中的执行结果如下：可以看出性能还是很高的，超过了99.92%的用户，内存消耗不大。它的核心代码在push方法中。首先将原来的最小值和最新的最小值依次入栈。出栈时判断入栈元素是否为最小值。如果是最小值，则将当前最小值指向栈顶元素，并将栈顶元素弹出，从而得到下一个新的最小值。实现代码2如果我们不想使用数组的自定义栈，也可以使用Java内置的栈Stack来实现这个功能。代码如下：classMinStack{privateStack
