一、栈基础知识

1. 栈概念

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

2. Java中的栈

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

二、栈知识扩展

1. 栈的应用

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

2. 单调栈法

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

栈题目 | 栈的应用

题目一：后缀表达式

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

题目分析

难度： ⭐🐇🐇🐇🐇
思路： 以样例为例，当遇到 * 时，计算 * 前的两个数的结果；此时

参考代码
public int evalReversePolishNotation(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    for (String token : tokens) {
        if ("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token)) {
            // 取出最新两个数，并进行计算
            Integer num1 = stack.pop();
            Integer num2 = stack.pop();
            int calculate = calculate(num2, num1, token);
            // 计算结果重新放入栈
            stack.push(calculate);
        } else {
            // 数字直接放入栈
            stack.push(Integer.parseInt(token));
        }
    }
    return stack.pop();
}

public int calculate(int a, int b, String operator) {
    switch (operator) {
        case "+":
            return a + b;
        case "-":
            return a - b;
        case "*":
            return a * b;
        case "/":
            return a / b;
        default:
            return 0;
    }
}
Tips：2024-02-05 22:21
题目二：小行星碰撞

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

图 5.1

题目分析

难度： ⭐⭐🐇🐇🐇
思路： 遍历时，新的元素需要倒叙和旧元素比较，并且将比其绝对值小的消除，直到遇到比自己大的被消除或者相等一起消除。不难看出，使用栈能很好的处理这种情况，右移的数放入栈，左移的数遍历栈。当栈空了时，将当前左移的数放入栈；当栈顶元素比当前数绝对值大时，不对栈进行处理；当栈顶元素小于当前数绝对值时，去除栈顶元素，并继续遍历栈；相等时，去除栈顶元素，停止遍历。

参考代码
public int[] asteroidCollision(int[] planets) {
    Stack<Integer> stack = new Stack<>();
    for (int planet : planets) {
        if (planet > 0) {
            // 元素为正，直接加入栈
            stack.push(planet);
        } else {
            // 元素为负，对比栈顶元素
            while (!stack.isEmpty()) {
                Integer pop = stack.pop();
                if (pop > 0) {
                    int sum = planet + pop;
                    if (sum > 0) {
                        // 如果和为正表明栈顶元素更大，将栈顶元素放回
                        stack.push(pop);
                        break;
                    } else if (sum == 0) {
                        // 相同时，抵消，都不放如栈
                        break;
                    } else if (stack.isEmpty()) {
                        // 如果栈已经空了也没找到比自己大的元素，则将新元素放回栈顶
                        stack.push(planet);
                    }
                } else {
                    // 负数则放回栈顶
                    stack.push(pop);
                    break;
                }
            }
        }
    }
    int[] result = new int[stack.size()];
    for (int i = stack.size() - 1; i >= 0; i--) {
        result[i] = stack.pop();
    }
    return result;
}
Tips：2024-03-11 18:25
题目三：每日温度

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

题目分析

难度： ⭐⭐🐇🐇🐇
思路： 首先可以想到暴力求解，从当前元素开始遍历后面的所有元素，记录第一次遇到比当前元素大的元素出现的下标，并计算间距。但是由于复杂度较高，这里可以考虑使用栈进行处理。首先，元素下标作为栈的元素入栈，后续元素需要和栈顶进行比较，如果新元素比栈顶元素大，那么栈顶元素所求天数就是当前元素的下标减去栈顶元素下标。这里的栈存储的元素指针对应的值是有序的，且是降序的，如果出现升序，则将比其小的依次出栈，依次出栈的元素所对应的所求第一次出现高温的时间就一定是当前元素所对应的时间。

参考代码
public int[] getTemperature(int[] temps) {
    int[] res = new int[temps.length];
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < temps.length; i++) {
        while (!stack.isEmpty()) {
            Integer peek = stack.peek();
            if (temps[i] > temps[peek]) {
                // 栈顶温度小于当前温度，计算栈顶元素的天数，出栈继续遍历
                res[peek] = i - peek;
                stack.pop();
            } else {
                // 栈顶温度大于当前温度，跳过
                break;
            }
        }
        // 将新元素放入栈
        stack.push(i);
    }
    return res;
}
Tips：2024-03-24 21:35
题目四：直方图最大矩形面积

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

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

题目分析

难度： ⭐⭐⭐🐇🐇
思路：
  计算最大的矩形面积，即以某一个矩形为顶而形成的新的矩形的面积。而以该矩形为顶时，与其组成新矩形的相邻矩形一定是高于或等于当前矩形。也就是说寻找最大矩形面积，等同于计算每个矩形为顶而形成的新矩形的面积大小，而最大的即为所求。新矩形的高度为顶的矩形高度，而宽度由相邻的高度低于顶矩形的高度的矩形所处位置决定。
  以图 5.2为例，以第四个矩形为顶，往左找到第一个小于自己的矩形下标l = 1，而往右找到的是r = 5，所以宽度为r - l - 1 = 3，面积s = 3 * 4 = 12。
  根据这个思路，常规暴力模拟即可解决，但是时间复杂度会比较高O(n²)。在寻找比自己小的矩形时，不难发现主要的时间都用于寻找比自己短的矩形位置了，如果能很轻易的获取到比自己短的左右相邻矩形位置就能很高效的计算以某一个矩形为顶形成的最大面积了。
  这里可以借助单调栈来处理，我们在栈中只存储比当前栈顶矩形更高的元素；而短的元素，这正好是栈顶矩形的右侧第一个比栈顶矩形短的矩形；而栈顶矩形的下一个栈元素一定小于栈顶矩形，正好是栈顶矩形左侧第一个比栈顶矩形短的矩形；所以此时可以非常直接的计算处以栈顶矩形为顶形成的最大矩形面积：s = (r - l - 1) * h，计算后，栈顶元素被移除栈；同时为了获取矩形下标，这里栈存储的是矩形下标而非矩形高度（下标可以方便的获取高度，而高度无法获取下标）。
  当然，这样处理后栈依旧可能存在未被当作栈顶的矩形，所以此时应该按栈顶元素依次遍历计算面积。这里计算需要注意的是，剩余元素的 r 一定都是第一个栈顶元素的下标 +1（因为右侧不会有元素了），左侧是下一个元素下标（递增栈，下一个元素一定小于栈顶元素），而最后一个元素左侧的下标应为 - 1（左侧没有元素了），代码中因为 +1 和 -1 存在重复计算，可以简化一下。

参考代码
public int maxRectangleArea(int[] rectangles) {
    Stack<Integer> stack = new Stack<>();
    int res = 0;
    for (int i = 0; i < rectangles.length; i++) {
        Integer peek;
        // 如果栈不为空，且新矩形小于栈顶元素，遍历栈
        if (!stack.isEmpty() && rectangles[(peek = stack.peek())] >= rectangles[i]) {
            // 将所有大于新矩形的元素作为顶计算最大矩形面积
            while (peek != -1 && rectangles[peek] >= rectangles[i]) {
                // 栈顶元素出栈
                Integer pop = stack.pop();
                peek = stack.isEmpty() ? -1 : stack.peek();
                res = Math.max(res, (i - peek - 1) * rectangles[pop]);
            }
        }
        // 将新矩形下标入栈
        stack.push(i);
    }
    if (stack.isEmpty()) {
        return res;
    }

    // 剩余递增矩形
    Integer right = stack.peek();
    while (!stack.isEmpty()) {
        Integer pop = stack.pop();
        Integer left = stack.isEmpty() ? -1 : stack.peek();
        res = Math.max(res, (right - left) * rectangles[pop]);
    }
    return res;
}
Tips：2024-06-14 16:53
题目五：矩阵中的最大矩形

  请在一个由0、1组成的矩阵中找出最大的只包含1的矩形并输出它的面积。例如，在图 5.3的矩阵中，最大的只包含1的矩阵如阴影部分所示，它的面积是6。

图 5.3 一个由0、1组成的矩阵

题目分析

难度： ⭐⭐⭐🐇🐇
思路：
  这个题目还是关于最大矩形的，它们之间有没有某种联系？如果能从矩阵中找出直方图，那么就能通过计算直方图中的最大矩形面积来计算矩阵中的最大矩形面积。
  直方图是由排列在同一基线上的相邻柱子组成的图形。由于题目要求矩形中只包含数字 1，因此将矩阵中上下相邻的值为 1 的格子看成 直方图中的柱子。如果分别以图 5.3 中的矩阵的每行为基线，就可以得到 4 个由数字 1 的格子组成的直方图，如图 5.4 所示。
  在将矩阵转换成多个直方图之后，就可以计算并比较每个直方图的最大矩形面积，所有直方图中的最大矩形也是整个矩阵中的最大矩形。例如，图 5.4(c) 的直方图中的最大矩形（阴影部分）也是图 5.3 中矩阵的最大矩形。

图 5.4

参考代码
public int maxMatrixArea(int[][] matrix) {
    int res = 0;
    int[][] temp = new int[matrix.length][matrix[0].length];
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[i].length; j++) {
            if (i == 0) {
                temp[i][j] = matrix[i][j];
            } else {
                temp[i][j] = matrix[i][j] == 0 ? 0 : temp[i - 1][j] + matrix[i][j];
            }
        }
        // maxRectangleArea 为上题函数
        res = Math.max(res, maxRectangleArea(temp[i]));
    }
    return res;
}
Tips：2024-06-14 16:53

三、章节小结

  栈是一种常见的数据结构；栈的插入、删除操作都发生在栈的顶部。在栈中插入、删除数据的顺序为“后入先出”，即最后添加的数据最先被删除。Java 的类型 Stack 实现了栈的功能。
  在分析解决问题时，如果一个数据集合的添加、删除操作满足“后入先出”的特点，那么可以用栈来实现这个数据集合。