今天和大家聊的问题叫做 最小栈，我们先来看题面：https://leetcode-cn.com/problems/min-stack/
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
题意
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) —— 将元素 x 推入栈中。
- pop() —— 删除栈顶的元素。
- top() —— 获取栈顶元素。
- getMin() —— 检索栈中的最小元素。
样例
输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] 输出： [null,null,null,null,-3,null,0,-2] 解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
解题
思路：用一个int型成员变量min记录当前栈中的最小值
public class MinStack { private LinkedList<Integer> stack; List<Integer> array; int min; public MinStack() { stack = new LinkedList<>(); array = new ArrayList<>(); min = Integer.MAX_VALUE; } public void push(int x) { stack.push(x); array.add(x); min = Math.min(min, x); } public void pop() { int num = stack.pop(); array.remove(array.size() - 1); if(array.size() > 0) { min = array.get(0); for (int i = 0; i < array.size(); i++) { if(min > array.get(i)) { min = array.get(i); } } }else { min = Integer.MAX_VALUE; } } public int top() { return stack.peek(); } public int getMin() { return min; } }
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。
