ps上做网站/南昌搜索引擎优化

题目：

https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/

解题思路：

题目要求实现一个包含min()函数的栈，min()函数的作用是返回栈中的最小值，因此我们可以想到使用一个辅助的数据结构来进行实现。

首先我们想到的是一个小根堆或者是一个排序的List，但是题目的要求是时间复杂度为O(1)，这就排除了大多数的解决办法了。

想到时间复杂度为O(1),想必大多数同学都会想到用HashMap,但是再看看案例，再删除一个最小值时还要重新寻找最小值，不可能把Map按从小到大排列吧，因此又排除了Map实现。

但是除了Map的时间复杂度为O(1)，还有其他的数据结构，比如队列、栈。

首先看队列，先进先出，我们不能预知先进的一定是最小的，进而先出的也不一定是最小的，因此排除队列。

接下来只剩栈了，后进先出，我们可以决定后进的一定比先进的小，因此我们就能够实现先出的一定是最小的，所以栈合适！

综上，我们增加一个辅助的栈用来存储最小值，当判断压入的数据小于min栈的栈顶元素时，压入min栈一份，反之不压入，在弹出数据时进行判断min栈和数据栈的栈顶元素是否相等，相等则全部弹出，反之则只弹出数据栈中的元素。

图解：

压入数据:

弹出数据：

代码：

算法：

/*** @desc: 包含min函数的栈* @author: YanMingXin* @create: 2021/8/26-15:48**/
public class MinStack {private Stack<Integer> stack;private Stack<Integer> stack1;/*** initialize your data structure here.*/public MinStack() {stack = new Stack<>();stack1=new Stack<>();}public void push(int x) {stack.push(x);if (stack1.empty() || stack1.peek() >= x) {stack1.add(x);}}public void pop() {if (stack.pop().equals(stack1.peek())) {stack1.pop();}}public int top() {return stack.peek();}public int min() {return stack1.peek();}
}

测试：

public static void main(String[] args) {MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-2);minStack.push(-3);//--> 返回 -3.System.out.println(minStack.min());minStack.pop();//  --> 返回 0.System.out.println(minStack.top());//--> 返回 -2.System.out.println(minStack.min());
}

over~