包含min函数的栈

题目描述

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

思路一：不改变原栈的顺序，时间复杂度为 O(n)

idea: 本题需要重新自定义 push,pop,top,min 方法，使得能够通过 min 方法随时得到当前栈中的最小元素。

首先如果我们不考虑这是一个栈，而是一个普通的数组，那么就很简单，我们只需要定义一个数 minNumber 存储当前数组中的最小值。遍历整个数组，如果当前数小于最小值 min，那么就更新最小值，否则就继续遍历。

那么我们能不能将这种思想转换到栈中呢？首先我们必须清楚栈的特点：“先进后出，后进先出”。如果我们依次将栈中的元素弹出来和 minNumber 比较，如果小于最小值 minNumber, 就更新 minNumber, 否则就继续弹出。这种思想事实上是可以借鉴的。但是有个问题是当我们把最小值找到了，但是这个时候栈也空了。所以我们就需要一个辅助栈来暂时存储弹出来的数，将栈里面的数弹空了，最小值也找到了，那么就将辅助栈里面的数又重新压入原来的栈中。这样两次出栈和入栈的过程也不会改变原来栈中的顺序。

import java.util.Stack;
 
public class Solution {
    
      // 创建两个栈对象，一个用于存储原栈数据，一个用于暂时辅助存储数据
      Stack<Integer> stack = new Stack<Integer>();
      Stack<Integer> subStack = new Stack<Integer>();
 
    
    public void push(int node) {stack.push(node);
        
    }
    
    //pop 操返回栈顶元素的同时会 remove 栈顶元素
    public void pop() {int p = stack.pop();
        
    }
    
    // 这里返回栈的顶部元素，但是不会 remove 栈顶元素
    public int top() {int topNumber = stack.peek();
        return topNumber;
        
    }
    
    public int min() {
        int minNumber = Integer.MAX_VALUE;
        // 依次取出栈里面的数直到栈为空
        while(stack.isEmpty() != true){
            // 得到栈顶元素
            int number = stack.pop();
            if(minNumber > number){minNumber = number;}
            // 弹出一个，压入一个
            subStack.push(number);
        }
        // 最后将辅助栈中的元素再重新压入原来的栈里
        while(subStack.isEmpty() != true){stack.push(subStack.pop())
        }
        
        return minNumber;
        
    }
}

思路二

利用辅助栈存储栈中对应元素的最小值，使得辅助栈的栈顶永远是最小值，从而可以以 o(1) 的时间复杂度获取到最小值

package code;

import javax.activation.MailcapCommandMap;
import java.util.Stack;

public class Stacke1 {Stack stack = new Stack<Integer>();
    Stack subStack = new Stack<Integer>();
    public void push(int node) {stack.push(node);
        // 这里的短路或不能调换位置
        if(subStack.isEmpty() || node < (int)subStack.peek()){subStack.push(node);
        } else {subStack.push(subStack.peek());
        }
    }

    public void pop() {stack.pop();
        subStack.pop();}

    public int top() {return (int) stack.peek();}

    public int min() {return (int)subStack.peek();}

}