LCR036-LCR040栈的应用

剑指offer（专项突破版）6.2 栈的应用

逆波兰表达式求值

分析

如果是数字就入栈，如果是符号就出栈两个数字来做运算。

class Solution {
public:
    int calculate(string op, int num1, int num2){
        if(op == "+")
            return num2 + num1;
        else if(op == "-")
            return num2 - num1;
        else if(op == "*")
            return num2 * num1;
        else if(op == "/")
            return num2 / num1;
        else
            return 0;
    }
    int evalRPN(vector<string>& tokens) {
        stack<int> stack;
        for(int i = 0; i < tokens.size(); i++){
            string token = tokens[i];
            if(token == "+" || token == "-" || token == "*" || token == "/"){
                int num1 = stack.top();
                stack.pop();
                int num2 = stack.top();
                stack.pop();
                int res = calculate(token, num1, num2);
                stack.push(res);
            }
            else{
                stack.push(stoi(token));
            }
        }
        return stack.top();
    }
};

• 时间复杂度：如果输入数组的长度是n，那么对其中的每个字符串都有一次push操作；如果是操作符，那么还需要进行数学计算和两次push操作。由于每个push操作、pop操作和数学计算都是O（1），因此总体时间复杂度是O（n）。
• 空间复杂度：由于栈中可能有O（n）个操作数，因此这种解法的空间复杂度也是O（n）。

行星碰撞

分析

如果一颗小行星向右飞行，那么可以将它入栈。如果一颗小行星是向左飞行的，而位于栈顶的小行星向右飞行，那么它将与位于栈顶的小行星相撞。如果位于栈顶的小行星较小，那么它将爆炸消失，也就是说它将出栈。然后判断它是否将与下一颗位于栈顶的小行星相撞。如果小行星与栈中所有小行星相撞之后仍然没有爆炸消失，那么将它入栈。

class Solution {
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
        stack<int> stack;
        for(int i = 0; i < asteroids.size(); i++){
            // 如果是向右飞行，则入栈
            if(asteroids[i] > 0){
                stack.push(asteroids[i]);
            }
            // 如果向左飞行
            else{
                // 如果栈顶向右飞行且小于该行星
                while(!stack.empty() && stack.top() > 0 && stack.top() < abs(asteroids[i])){
                    stack.pop();
                }
                // 如果等于
                if(!stack.empty() && stack.top() > 0 && stack.top() == abs(asteroids[i])){
                    stack.pop();
                }
                else if(stack.empty() || stack.top() < 0){
                    stack.push(asteroids[i]);
                }
            }
        }
        // 写入vector
        vector<int> res;
        while(!stack.empty()){
            res.push_back(stack.top());
            stack.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

• 时间复杂度：假设有n颗小行星。上述代码中有一个嵌套的二重循环，它的时间复杂度是不是O（n2）？由于每颗小行星只可能入栈、出栈一次，因此时间复杂度是O（n）。
• 空间复杂度：O（n）。

LCR038.每日温度

分析

• 入栈：当栈为空，或者当前值小于栈顶；
• 出栈：当前值大于栈顶，可以计算出差值，弹出，再检查下一个栈顶。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> stack;
        int n = temperatures.size();
        vector<int> res(n);
        for(int i = 0; i < n; i++){
            // 出栈
            while(!stack.empty() && temperatures[i] > temperatures[stack.top()]){
                res[stack.top()] = i - stack.top();
                stack.pop();
            }
            // 入栈
            stack.push(i);
        }
        return res;
    }
};

• 时间复杂度：假设输入数组的长度为n。虽然上述代码中有一个嵌套的二重循环，但它的时间复杂度是O（n），这是因为数组中每个温度入栈、出栈各1次。
• 空间复杂度：O(n)

LCR039.柱状图中最大的矩形

蛮力法

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        int res = 0;
        for(int i = 0; i < n; i++){
            int minH = heights[i];
            for(int j = i; j < n; j++){
                int w = j - i + 1;
                minH = min(minH, heights[j]);
                int area = w * minH;
                res = max(res, area);
            }
        }
        return res;
    }
};

• 时间复杂度：$O(n^2)
• 空间复杂度：O(1)

蛮力法无法通过所有测试点。

分治法

直方图中最矮的柱子在数组中的下标是5，它的高度是1。这个直方图的最大矩形有3种可能。第1种是矩形通过这根最矮的柱子。通过最矮的柱子的最大矩形的高为1，宽是7。第2种是矩形的起始柱子和终止柱子都在最矮的柱子的左侧，也就是从下标为0的柱子到下标为4的柱子的直方图的最大矩形。第3种是矩形的起始柱子和终止柱子都在最矮的柱子的右侧，也就是从下标为6的柱子到下标为7的柱子的直方图的最大矩形。第2种和第3种从本质上来说和求整个直方图的最大矩形面积是同一个问题，可以调用递归函数解决。

class Solution {
public:
    int largestArea(vector<int>& heights, int low, int high) {
        // 递归结束条件
        if(low == high){
            return 0;
        }
        if(low+1 == high){
            return heights[low];
        }
        // 找到区间内最小的值
        int minIndex = low;
        for(int i = low; i < high; i++){
            if(heights[i] < heights[minIndex]){
                minIndex = i;
            }
        }
        // 计算面积
        int area = (high - low) * heights[minIndex];
        int left = largestArea(heights, low, minIndex);
        int right = largestArea(heights,minIndex+1,high);

        // 返回最大值
        int res = max(area, left);
        res = max(res, right);
        return res;
    }
    int largestRectangleArea(vector<int>& heights) {
        return largestArea(heights, 0, heights.size());
    }
};

• 时间复杂度：假设输入数组的长度为n。如果每次都能将n根柱子分成两根柱子数量为n/2的子直方图，那么递归调用的深度为O（logn），整个分治法的时间复杂度是O（nlogn）。但如果直方图中柱子的高度是排序的（递增排序或递减排序），那么每次最矮的柱子都位于直方图的一侧，递归调用的深度就是O（n），此时分治法的时间复杂度也变成$O（n^2）$。
• 空间复杂度：基于递归的分治法需要消耗内存来保存递归调用栈，空间复杂度取决于调用栈的深度，因此这种分治法的平均空间复杂度是O（logn），最坏情况下的空间复杂度是O（n）。

这种方法也无法通过所有的测试点。

单调栈法

如果当前扫描到的数字比栈顶大，则入栈；反之则将栈顶出栈，并计算以它为顶的矩形面积。找到每个柱子左边第一个比自己矮的，和右边第一个比自己矮的，这两个矮的之间的距离都比这个柱子高或者相等，就能算出以这个柱子为高最大的面积。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> stack;
        stack.push(-1);
        int maxArea = 0;
        // 遍历
        for(int i = 0; i < heights.size(); i++){
            // 出栈，计算以栈顶为顶的最大面积
            while(stack.top()!=-1 && heights[stack.top()] >= heights[i]){
                int h = heights[stack.top()];
                stack.pop();
                int w = i - stack.top() - 1;
                maxArea = max(maxArea, h*w);
            }
            stack.push(i);
        }
        // 栈中剩余元素
        while(stack.top()!=-1){
            int h = heights[stack.top()];
            stack.pop();
            int w = heights.size() - stack.top() - 1;
            maxArea = max(maxArea, h*w);
        }
        return maxArea;
    }
};

• 时间复杂度：假设输入数组的长度为n。直方图的每根柱子都入栈、出栈一次，并且在每根柱子的下标出栈时计算以它为顶的最大矩形面积，这些操作对每根柱子而言时间复杂度是O（1），因此这种单调栈法的时间复杂度是O（n）。
• 空间复杂度：这种解法需要一个辅助栈，栈中可能有O（n）根柱子在数组中的下标，因此空间复杂度是O（n）。

LCR040.最大矩形

分析

先把矩阵转换为直方图，再利用上一题中单调栈方法。

class Solution {
public:
    int largestArea(vector<int> heights){
        int maxArea = 0;
        stack<int> stack;
        stack.push(-1);
        for(int i = 0; i < heights.size(); i++){
            while(stack.top()!=-1 && heights[stack.top()] >= heights[i]){
                int h = heights[stack.top()];
                stack.pop();
                int w = i - stack.top() - 1;
                maxArea = max(maxArea, h*w);
            }
            stack.push(i);
        }
        // 栈中剩余元素
        while(stack.top() != -1){
            int h = heights[stack.top()];
            stack.pop();
            int w = heights.size() - stack.top() - 1;
            maxArea = max(maxArea, h*w);
        }
        return maxArea;
    }
    int maximalRectangle(vector<string>& matrix) {
        int row = matrix.size();
        if(row == 0 || matrix[0].size() == 0){
            return 0;
        }

        vector<int> heights(matrix[0].size(), 0);
        int maxArea = 0;
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[0].size(); ++j) {
                if (matrix[i][j] == '0') {
                    heights[j] = 0;
                }
                else {
                    heights[j] += 1;
                }
            }
            // 对每一个直方图求最大面积
            maxArea = max(maxArea, largestArea(heights));
        }
        return maxArea;
    }
};

• 时间复杂度：假设输入的矩阵的大小为m×n。该矩阵可以转换成m个直方图。如果采用单调栈法，那么求每个直方图的最大矩形面积需要O（n）的时间，因此这种解法的时间复杂度是O（mn）。
• 空间复杂度：用单调栈法计算直方图中最大矩阵的面积需要O（n）的空间，同时还需要一个长度为n的数组heights，用于记录直方图中柱子的高度，因此这种解法的空间复杂度是O（n）。

总结

本章介绍了栈这种常见的数据结构。栈的插入、删除操作都发生在栈的顶部。在栈中插入、删除数据的顺序为“后入先出”，即最后添加的数据最先被删除。