LeetCodeHot100——155.最小栈

题目链接放在这里了155. 最小栈 - 力扣LeetCode这道题的思路就是要我们实现一个最小栈和它的基本几个功能最小栈就是在一个栈的基础上可以让我们知道这个栈任意时刻的最小值。我最初是想在一个栈的基础上加上一个属性用来存储最小值如果你也这么想那么你就想的太简单了如果栈里有5个元素最小值肯定是确定了呗那如果我们这时候pop了呢那下一个最小值怎么确认难道还要存储倒数第二小的做备份吗那倒数第二小的就不用更新了吗依次往复我们是不是要记录从开始到结尾每个元素在栈顶时对应的最小值啊那这样的话我们是不是就可以搞一个同步队列啊根据栈里的对应关系记录每个位置对应的最小值这样是可以实现的还有就是我们可以通过数组或者map的形式我们的栈中存储的不再是简单的一个数字了而是多个map或者多个大小为2的小数组这样我们在push的时候如果栈为空那就直接push(value,value)如果不为空那就peek()一下前一个的最小值和这次要push的值做比较取较小值作为当前值对应的最小值这种思路下来我们在查看最小值的时候只需要peek然后查看最小值对应位置的元素就好了这样栈中的每个元素都有其在栈顶时刻的最小值和value了下面是我的方法我是使用了map主要是想熟悉一下map的api在我们不知道key值的时候想按序获取map的Key和Value使用map.entrySet().iterator().next().getValue()/getKey()来操作class MinStack { private DequeMapInteger,Integer stack; public MinStack() { stack new LinkedList(); } public void push(int value) { MapInteger,Integer cur new HashMap(); if(stack.isEmpty()){ cur.put(value,value); }else{ int t stack.peek().entrySet().iterator().next().getValue(); cur.put(value,Math.min(value,t)); } stack.push(cur); } public void pop() { if(!stack.isEmpty()){ stack.pop(); } } public int top() { return stack.peek().entrySet().iterator().next().getKey(); } public int getMin() { return stack.peek().entrySet().iterator().next().getValue(); } } /** * Your MinStack object will be instantiated and called as such: * MinStack obj new MinStack(); * obj.push(value); * obj.pop(); * int param_3 obj.top(); * int param_4 obj.getMin(); */