255.最小栈

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

255.最小栈

解题思路：

package leadcode;import java.util.LinkedList;/*** @author : icehill* @description : 最小栈* 设计一个支持 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.* 来源：力扣（LeetCode）* 链接：https://leetcode-cn.com/problems/min-stack* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。* 解题思路：* 1.辅助栈，栈顶存储当前最小元素（入栈的时候判断并存储，出栈的时候也要对于判断出栈）* 时间复杂度：O(1) 空间复杂度：O(n)* 2.使用一个栈，栈存储Node，Node保存当前值val跟当前minVal值* 3.自定义栈：使用链表实现（跟2类似，链表节点保存当前值val跟最小值minVal）* @date : 2021-05-23*/
public class Solution255 {public static void main(String[] args) {MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);System.out.println(minStack.getMin());minStack.pop();System.out.println(minStack.top());System.out.println(minStack.getMin());MinStack2 minStack2 = new MinStack2();minStack2.push(-2);minStack2.push(0);minStack2.push(-3);System.out.println(minStack2.getMin());minStack2.pop();System.out.println(minStack2.top());System.out.println(minStack2.getMin());}/*** 辅助栈*/public static class MinStack {LinkedList<Integer> stack;LinkedList<Integer> minStack;public MinStack() {stack = new LinkedList<>();minStack = new LinkedList<>();}public void push(int val) {stack.push(val);if (minStack.isEmpty() || minStack.peek() >= val) {minStack.push(val);}}public void pop() {int x = stack.pop();if (!minStack.isEmpty() && minStack.peek() == x) {minStack.pop();}}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}}/*** 自定义栈节点*/public static class MinStack2 {LinkedList<StackNode> stack;public MinStack2() {stack = new LinkedList<>();}public static class StackNode {int val;int minVal;public StackNode(int val, int minVal) {this.val = val;this.minVal = minVal;}}public void push(int val) {if (stack.isEmpty()) {stack.push(new StackNode(val, val));} else {stack.push(new StackNode(val, Math.min(val, stack.peek().minVal)));}}public void pop() {stack.pop();}public int top() {StackNode stackNode = stack.peek();return stackNode.val;}public int getMin() {StackNode stackNode = stack.peek();return stackNode.minVal;}}
}

这篇关于255.最小栈的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---