【栈】——最小栈

好的，下面我用更通俗的方式来给你解释一下这道“155. 最小栈”题目的意思以及代码的思路呀。

题目意思

想象一下你有一个特殊的盒子（这个盒子就好比是我们要设计的栈），这个盒子可以做几件事情：

1. 放东西进去（push操作）：你可以把各种小玩意儿（在这里就是整数啦，用 val 表示）放进这个盒子里。每次放进去一个东西，它就会堆在盒子里其他东西的上面。

2. 拿出最上面的东西（pop操作）：当你想把盒子最上面的那个小玩意儿拿出来的时候，就可以进行这个操作，拿出来之后，盒子里剩下的东西又会重新排列，原来在它下面的那个东西就变成最上面的了。

3. 看看最上面放的是什么东西（top操作）：不把最上面的东西拿出来，只是看一眼，知道现在盒子最上面放的是哪个小玩意儿。

4. 找出盒子里最小的那个小玩意儿（getMin操作）：这是这道题特殊的要求哦，就是在这个盒子里所有放进去过的小玩意儿当中，要能很快地（在常数时间内，也就是不管盒子里放了多少东西，找最小的这个操作花费的时间都差不多）找到最小的那个是啥。

代码思路

为了实现这个特殊盒子（最小栈）的这些功能，我们用了一个巧妙的办法，就是准备两个盒子（在代码里就是两个栈啦，分别叫做 stack 和 min_stack）来一起完成这些任务。

1. 初始化两个盒子（__init__ 函数）：

   • 一开始，我们先准备好两个空盒子，也就是创建两个空的栈 stack 和 min_stack。这两个盒子就是用来存放东西和记录最小东西的地方啦。

2. 放东西进盒子（push 函数）：

   • 当我们要往盒子里放一个新的小玩意儿（整数 val）的时候，我们先把它放进 stack 这个盒子里，就像把东西正常堆在一个盒子里一样，一个压着一个放进去。
   • 然后呢，我们还要看看这个新放进去的小玩意儿是不是比 min_stack 这个盒子里目前最上面（也就是栈顶）的小玩意儿还要小或者一样小呀。要是 min_stack 这个盒子还是空的，那肯定这个新放进去的 val 就是目前最小的啦，就直接把 val 也放进 min_stack 这个盒子里。要是 min_stack 不是空的，而且 val 小于等于它栈顶的那个小玩意儿，那也把 val 放进 min_stack 里。这样做的目的就是让 min_stack 这个盒子里的栈顶元素始终是 stack 这个大盒子里所有放进去的小玩意儿当中最小的那个哦。

3. 拿出最上面的东西（pop 函数）：

   • 首先从 stack 这个盒子里把最上面的那个小玩意儿拿出来（用 pop 操作），把拿出来的这个小玩意儿先记下来，叫做 popped_val。
   • 然后我们看看这个 popped_val 和 min_stack 这个盒子里最上面（栈顶）的小玩意儿是不是一样呀。要是一样的话，那就说明我们刚才从 stack 里拿出来的这个小玩意儿就是目前最小的那个，现在要把它拿出来了，所以我们也要从 min_stack 这个盒子里把它的栈顶元素也拿出来，这样 min_stack 里剩下的栈顶元素就还是 stack 里剩下的小玩意儿当中最小的那个啦。

4. 看看最上面放的是什么东西（top 函数）：

   • 很简单啦，直接看看 stack 这个盒子里最上面（栈顶）放的是哪个小玩意儿就行啦，所以就返回 stack 的栈顶元素就可以了。

5. 找出盒子里最小的那个小玩意儿（getMin 函数）：

   • 因为我们一直让 min_stack 这个盒子里的栈顶元素是 stack 这个大盒子里所有小玩意儿当中最小的那个，所以要找最小的小玩意儿，直接看看 min_stack 的栈顶元素就行啦，就返回 min_stack 的栈顶元素哦。

这样通过两个盒子（两个栈）的配合，我们就实现了这个特殊的盒子（最小栈）的所有功能啦，既能正常放东西、拿东西、看最上面的东西，又能很快地找到里面最小的那个东西哦。希望这样通俗的解释能让你更清楚这道题和代码的思路呀，如果还有不明白的地方可以随时问哦。

原文地址：https://blog.csdn.net/weixin_47868976/article/details/143809737

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！