算法思维训练（五）| 栈💭-工具盒子

一、栈基础知识 {#一-栈基础知识}

1. 栈概念 {#1--栈概念}

栈是一种常用的数据结构，它最大的特点是"后入先出"，即后进入栈中的元素最先出来。为了确保"后入先出"的顺序，栈的插入和删除操作都发生在栈顶。

2. Java中的栈 {#2--Java中的栈}

Java的库中提供了实现栈的类型Stack。常见方法如下：
- push(e)：元素e入栈。
- pop：位于栈顶的元素出栈，并返回该元素。
- peek：返回位于栈顶的元素，该元素不出栈。
函数pop和peek都能返回位于栈顶的元素，但函数pop会将位于栈顶的元素出栈，而函数peek不会。Stack的函数push、pop和peek的时间复杂度都是O(1)。

二、栈知识扩展 {#二-栈知识扩展}

1. 栈的应用 {#1--栈的应用}

一般的，在记录数据时，通常我们会将数据先保存到一个数据容器中以便后续使用。如果数据保存的顺序和使用顺序相反，那么最后保存的数据最先使用，这个时候，数据的使用方式与栈的"后入先出"特性非常契合，可以考虑通过栈来保存数据。

2. 单调栈法 {#2--单调栈法}

多数时候，保存在栈中的数据是有序的。根据题目的不同，栈中的数据既可能是递增排序的，也可能是递减排序的。因此，而这种用排序的栈解决问题的方法，被人称为单调栈法。

栈题目 | 栈的应用 {#栈题目---栈的应用}

题目一：后缀表达式 {#题目一-后缀表达式}

后缀表达式是一种算术表达式，它的操作符在操作数的后面。输入一个用字符串数组表示的后缀表达式，请输出该后缀表达式的计算结果。假设输入的一定是有效的后缀表达式。例如，后缀表达式["2"，"1"，"3"，"\*"，"+"]对应的算术表达式是2+1\*3，因此输出它的计算结果5。

题目分析 {#题目分析}

难度： 略
思路： 略

参考代码 {#参考代码}

Tips：2024-02-05 22:21 {#Tips-2024-02-05-22-21}

题目二：小行星碰撞 {#题目二-小行星碰撞}

输入一个表示小行星的数组，数组中每个数字的绝对值表示小行星的大小，数字的正负号表示小行星运动的方向，正号表示向右飞行，负号表示向左飞行。如果两颗小行星相撞，那么体积较小的小行星将会爆炸最终消失，体积较大的小行星不受影响。如果相撞的两颗小行星大小相同，那么它们都会爆炸消失。飞行方向相同的小行星永远不会相撞。求最终剩下的小行星。例如，有6颗小行星[4，5，-6，4，8，-5]，如图6.2所示（箭头表示飞行的方向），它们相撞之后最终剩下3颗小行星[-6，4，8]。

题目分析 {#题目分析-}

难度： 略
思路： 略

参考代码 {#参考代码-}

Tips：2024-03-11 18:25 {#Tips-2024-03-11-18-25}

题目三：每日温度 {#题目三-每日温度}

输入一个数组，它的每个数字是某天的温度。请计算每天需要等几天才会出现更高的温度。例如，如果输入数组[35，31，33，36，34]，那么输出为[3，1，1，0，0]。由于第1天的温度是35℃，要等3天才会出现更高的温度36℃，因此对应的输出为3。第4天的温度是36℃，后面没有更高的温度，它对应的输出是0。其他的以此类推。

题目分析 {#题目分析--}

难度： 略
思路： 略

参考代码 {#参考代码--}

Tips：2024-03-24 21:35 {#Tips-2024-03-24-21-35}

题目四：直方图最大矩形面积 {#题目四-直方图最大矩形面积}

直方图是由排列在同一基线上的相邻柱子组成的图形。输入一个由非负数组成的数组，数组中的数字是直方图中柱子的高。求直方图中最大矩形面积。假设直方图中柱子的宽都为1。例如，输入数组[3，2，5，4，6，1，4，2]，其对应的直方图如图5.1所示，该直方图中最大矩形面积为12，如阴影部分所示。

图5.1 柱子高度分别为[3，2，5，4，6，1，4，2]的直方图