本文共 1344 字，大约阅读时间需要 4 分钟。

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

思路如下:

2.当元素要出栈的时候，首先判断主栈要出栈的元素是不是和辅助栈的栈顶元素相同，如果是，则代表当前出栈的元素是最小的元素，那么就需要将辅助栈的元素也出栈，让辅助栈的下一个栈顶元素成为最小的元素，栈元素出栈。

3.求最小的元素，只需要将辅助栈的栈顶元素出栈即可。

import java.util.Stack;public class Solution {
       public Stack
   
     mainStack = new Stack();    public Stack
    
      stackTemp = new Stack();    public void push(int node) {
           //判断辅助栈是否为空,如果为空，就代表第一次入栈        if(stackTemp.empty()){
               stackTemp.push(node);        }else{
                 //如果不为空，就代表需要判断当前入栈元素与辅助栈的元素进行比较,此时辅助栈栈顶代表最小的元素             if(node<=stackTemp.peek()){
                   stackTemp.push(node);             }          }                       mainStack.push(node);    }        public void pop() {
           //当主栈要出栈的时候，需要判断要出栈的元素是不是最小的元素，如果是就要把辅助栈中的栈顶元素出栈，然后次小元素        //作为出完栈后的最小元素        if(!stackTemp.empty()&&!mainStack.empty()){
               if(mainStack.peek()==stackTemp.peek()){
               stackTemp.pop();        }            mainStack.pop();        }            }        public int top() {
           if(!mainStack.empty()){
               return (int)mainStack.peek();        }else{
               return 0;        }          }        public int min(){
           return stackTemp.pop();    }                }
    
   

转载地址：http://nrlen.baihongyu.com/