题解

描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，并且调用 min函数、push函数 及 pop函数 的时间复杂度都是 O(1)

push(value):将value压入栈中

pop():弹出栈顶元素

top():获取栈顶元素

min():获取栈中最小元素

示例

输入: ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]

输出: -1,2,1,-1

解析:

"PSH-1"表示将-1压入栈中，栈中元素为-1

"PSH2"表示将2压入栈中，栈中元素为2，-1

“MIN”表示获取此时栈中最小元素==>返回-1

"TOP"表示获取栈顶元素==>返回2

"POP"表示弹出栈顶元素，弹出2，栈中元素为-1

"PSH-1"表示将1压入栈中，栈中元素为1，-1

"TOP"表示获取栈顶元素==>返回1

“MIN”表示获取此时栈中最小元素==>返回-1

思路

本题的思路有点巧妙，这里利用了一个队列Deque，push()、pop()和top()方法都特别简单，因为栈本身就有对应的方法，难点在于怎么获得并返回此时栈中最小的元素值。这里使用了特殊的结构队列Deque，每当push或者pop时，都会相对应地在队列d的末尾添加或者删除元素。在min()方法中，遍历这个队列，大小为d.size()，则做d.size()次的取出队头元素，将这个元素值添加进list数组后，又将这个元素插入到队尾的操作，这样子就保证了队列的原样，没有改变里面的结构和元素，同时还获取到了队列中所有的值。最后就是遍历这个数组list，找到最小值并返回。注意一个细节：每次取完最小值后必须清空这个list数组，否则还会存有数据，下次再次取最小值的时候，就不能保证取到的是当前队列的最小值了。

代码

import java.util.*;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Deque<Integer> d = new ArrayDeque<>();
    ArrayList<Integer> list = new ArrayList();
    
    public void push(int node) {
        stack1.push(node);
        d.addLast(node);
    }
    
    public void pop() {
        stack1.pop();
        d.pollLast();
    }
    
    public int top() {
        return stack1.peek();
    }
    
    public int min() {
        for(int i=0;i<d.size();i++){
            int a = d.pollFirst();
            list.add(a);
            d.addLast(a);
        }
        
        int a = list.get(0);
        for(int i=1;i<list.size();i++){
            if(list.get(i) < a){
                a = list.get(i);
            }
        }
        list.clear();
        return a;
    }
}