这道题评论区的大佬真是各抒己见啊,我也不知道用栈来实现对不对,但是看到一个非常棒的用栈来实现的方法
class MinStack { private int min = Integer.MAX_VALUE; private Stack<Integer> stack; public MinStack() { stack = new Stack<>(); } public void push(int val) { //用一个变量来存最小值,如果存储的这个最小值比入栈元素大,就把原来的最小值入栈,再把当前元素的值存到min里 if(min >= val){ stack.push(min); min = val; } //当前元素入栈 stack.push(val); } public void pop() { if(stack.pop() == min){ min = stack.pop(); } } public int top() { return stack.peek(); } //直接返回min中的最小元素的值 public int getMin() { return min; } }
再来看看官方的栈
class MinStack { Deque<Integer> xStack; Deque<Integer> minStack; public MinStack() { xStack = new LinkedList<Integer>(); minStack = new LinkedList<Integer>(); minStack.push(Integer.MAX_VALUE); } public void push(int x) { xStack.push(x); minStack.push(Math.min(minStack.peek(), x)); } public void pop() { xStack.pop(); minStack.pop(); } public int top() { return xStack.peek(); } public int getMin() { return minStack.peek(); } }
上面的方法都会用到额外空间,来看看不用额外空间的吧
class MinStack { // 数组栈, [当前值, 当前最小值] private Stack<int[]> stack = new Stack<>(); public MinStack() { } public void push(int x) { if (stack.isEmpty()){ stack.push(new int[]{x, x}); }else { stack.push(new int[]{x, Math.min(x, stack.peek()[1])}); } } public void pop() { stack.pop(); } public int top() { return stack.peek()[0]; } public int getMin() { return stack.peek()[1]; } }
啊好难啊啊啊啊啊