Leetcode面试经典150题-155.最小栈

本文主要是介绍Leetcode面试经典150题-155.最小栈，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

解法都在代码里，不懂就留言或者私信

我写了两种解法，建议选择双栈的，感觉这才是考察点


/**一般解法：过个笔试没问题，建议用双栈的方法 */
class MinStack2 {/**至少应该有一个栈用于保存数据 对于push和pop以及top的话，如果不考虑从栈中获取最小元素，那就是单纯的栈但是因为这个获取最小元素的方法，我们就得准备一个结构用于存放最小值，我这里想到的是最小堆*/Stack<Integer> stack;PriorityQueue<Integer> heap;public MinStack2() {stack = new Stack<>();heap  = new PriorityQueue<>();}public void push(int val) {stack.push(val);heap.add(val);}public void pop() {Integer pop = stack.pop();heap.remove(pop);}public int top() {return stack.peek();}public int getMin() {return heap.peek();}
}/**最优解法：这大概才是人家的考点*/
class MinStack {/**至少应该有一个栈用于保存数据 对于push和pop以及top的话，如果不考虑从栈中获取最小元素，那就是单纯的栈但是因为这个获取最小元素的方法，我们就得准备一个结构用于存放最小值，我这里想到的是最小堆*//**用于做栈的常规操作的栈 */Stack<Integer> stack;/**minStack用来保存当前的最小值 */Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack  = new Stack<>();}public void push(int val) {/**stack无论如何是必须要放的*/stack.push(val);/**用于保存最小值的栈只有影响到最小值的时候才放，因为你加入导致最小值改变了那就让你进最小值如果你的出现不影响最小值，那你加入或者删除对于最小值没有任何影响，你进minStack干啥这里要特别注意等于的情况，如果等于minStack的栈顶元素是要入minStack，这里避免重复的只入了一个然后删除的时候直接删了，但是其实我们有好多个*//**如果minStack是空，那stack肯定也是空的，那val的加入就是最小值 */if(minStack.isEmpty() || val <= minStack.peek()) {minStack.push(val);}}public void pop() {if(stack.isEmpty()) {return;}/**无论如何，正常用于操作的栈还是要弹出的 */Integer pop = stack.pop();/**如果要弹出的刚好是当前最小值，则minStack弹出栈顶这里分为两种情况：1 这个值只有一个，那弹出了最小值就变了2. 这个值有多个，那弹出之后顶上这个数少一个总之弹出的前提是它是当前最小值 *//**这个地方注意要用equals，不能用== */if(!minStack.isEmpty() && minStack.peek().equals(pop)) {minStack.pop();}}/**要的是真实的栈顶值 */public int top() {return stack.peek();}/**最小值就是最小值栈的栈顶值 */public int getMin() {return minStack.peek();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/

运行结果