栈算法题目集合

leetcode71 简化路径

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。 在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。 请注意，返回的 规范路径 必须遵循下述格式： 始终以斜杠 '/' 开头。 两个目录名之间必须只有一个斜杠 '/' 。 最后一个目录名（如果存在）不能 以 '/' 结尾。 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。 返回简化后得到的规范路径。

题解

参考题解

leetcode150 逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 注意： 有效的算符为 '+'、'-'、'*' 和 '/' 。 每个操作数（运算对象）都可以是一个整数或者另一个表达式。 两个整数之间的除法总是 向零截断 。 表达式中不含除零运算。 输入是一个根据逆波兰表示法表示的算术表达式。 答案及所有中间计算结果可以用 32 位 整数表示。

题解

从左向右遍历，用栈存储数字，遇到符号出栈两个数字

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        long result = 0;
        stack<int> nums;
        for (string token : tokens) {
            if (token != "+" && token != "-" && token != "*" && token != "/") {
                nums.push(stoi(token));
                continue;
            }
            int n2 = nums.top();nums.pop();
            int n1 = nums.top();nums.pop();
            if (token == "+") {
                nums.push(n1 + n2);
            }
            else if (token == "-") {
                nums.push(n1 - n2);
            }
            else if (token == "*") {
                nums.push(n1 * n2);
            }
            else if (token == "/") {
                nums.push(n1 / n2);
            }
        }
        return nums.top();
    }
};

leetcode84 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。

单调栈获取两端更小值的索引

刚接触到题目以为与最大盛水量是相同解法，这题的不同之处在于面积取决于区间内的最小值，而不是两端的最小值 由此，对于柱高上升的区间，起始柱总能取其高计算面积，若新加入的柱高小于栈顶高，则表示已到达栈顶对应开区间的右端点，将栈顶弹出，新的栈顶表示开区间的左端点

int largestRectangleArea(vector<int>& heights) {
    int maxS = 0;
    // 方便计算开头与末尾的柱面积
    heights.insert(heights.begin(), 0);
    heights.emplace_back(0);
    int n = heights.size();
    // 单调栈
    stack<int> rise;
    rise.emplace(0);
    for (int i = 1; i < n; i ++) {
        // 触及右边界，出栈直到栈再次单调或为空
        while (! rise.empty() && heights[rise.top()] > heights[i]) {
            int h = heights[rise.top()]; rise.pop();
            int w = i - rise.top() - 1;
            maxS = max(maxS, h * w);
        }
        rise.emplace(i);
    }
    return maxS;
}

leetcode85 最大矩形

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

逐行求解最大矩形

int maximalRectangle(vector<vector<char>>& matrix) {
    int maxS = 0;
    int m = matrix.size(), n = matrix[0].size();
    vector<int> heights(n + 2, 0);
    stack<int> rise;
    // 遍历每一行
    for (int i = 0; i < m; i ++) {
        rise.emplace(0);
        // 计算当前高度
        for (int j = 0; j < n + 1; j ++) {
            if (j < n) {
                // 若为0则高度置0
                if (matrix[i][j] - '0') heights[j + 1] += 1;
                // 若为1高度加1
                else heights[j + 1] = 0;
            }
            // 区间判断
            while (! rise.empty() && heights[rise.top()] > heights[j + 1]) {
                int h = heights[rise.top()]; rise.pop();
                int w = (j + 1) - rise.top() - 1;
                maxS = max(maxS, h * w);
            }
            rise.emplace(j + 1);
        }
        while (! rise.empty()) rise.pop();
    }
    return maxS;
}

leetcode739 每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

单调递减栈

若当前温度比当前栈顶高，则必为最近一个高温，否则记录在栈中待找寻下一个高温

vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> ret(n, 0);
    stack<int> down;
    down.emplace(0);
    for (int i = 1; i < n; i ++) {
        while (! down.empty() && temperatures[down.top()] < temperatures[i]) {
            ret[down.top()] = i - down.top();
            down.pop();
        }
        down.emplace(i);
    }
    return ret;
}