的文章转载请联系程序员钱宇公众号。Leetcode:https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof"GitHub:https://gitee.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_23_MinStack/MinStack.java包含min函数的栈》题目描述：定义栈的数据结构，请实现一个min函数，可以获取栈中的最小元素这种类型在栈中，调用min、push、pop的时间复杂度是O(1)。示例：MinStackminStack=newMinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.min();-->return-3.minStack.pop();minStack.top();-->return0.minStack.min();-->return-2。提示：每个函数的总调用次数不超过20,000个值。另一个存储最小值。"普通栈的push()和pop()函数复杂度为O(1)；而min()函数获取栈的最小值需要遍历整个栈，复杂度为O(n).本题难点：将min()函数复杂度降低为0(1)，可以通过建立辅助栈来实现；数据栈A：栈A用于存放所有元素，并保证push()函数入栈，pop()函数出栈，得到栈顶()函数正常逻辑辅助栈B：存放所有非严格递减的元素在栈A中在栈B中，那么栈A中的最小元素总是对应于栈B的栈顶元素，即min()函数只需要返回栈顶元素即可。因此，只需尝试维护栈B的元素，使其保持非严格降序排列，然后min()函数的0(1)复杂度离子可以实现。函数设计：push(x)函数：重点是让栈B的元素保持非严格降序排列。将x压入堆栈A（即A.add(x)）；如果①栈B为空或者②x小于等于栈B的栈顶元素，则将x压入栈B（即B.add(x)）。pop()函数：重点是保持A栈和B栈的元素一致性，执行A栈出栈（即A.pop()），将出栈的元素记录为y；如果y等于B栈顶元素，执行B栈出栈（即B.pop()）。top()函数：直接返回栈A的栈顶元素，即returnA.peek()。min()函数：直接返回B栈顶元素即可，即returnB.peek()。复杂度分析：时间复杂度O(1)：push()、pop()、top()、min()四个函数的时间复杂度都是常量级别。空间复杂度O(N)：当有N个元素入栈时，辅助栈B在最坏情况下存储N个元素，使用O(N)的额外空间。》在Java代码中，由于Stack存放在int包装类Integer中，所以需要用equals()代替==来比较值是否相等，如果用==做这道题，不会被Integer的equals改写，是内部值的值，==如果在[-128,127]，会被缓存缓存，如果超过这个范围，比较的是对象是否是同一个包com.nateshao.sword_offer.topic_23_MinStack;importjava.util.Stack;/***@dateCreatedby邵同杰on2021/11/2821:38*@微信公众号程序员千语*@个人网站www.nateshao.cn*@博客https://nateshao.gitee.io*@GitHubhttps://github.com/nateshao*@Giteehttps://gitee.com/nateshao*描述：一个包含min函数的栈*思路：定义两个栈，一个用来存储输入的值，另一个存储最小值。*/publicclassMinStack{privateStack
