剑指offer专项突击版第12天

剑指 Offer II 036. 后缀表达式
题目直接给了后缀表达式，就直接算就行了。如果给的是中缀那么就需要转后缀再计算（转换的过程中计算可以直接拿到结果，若转后缀过程中不直接计算直接把符号也压入栈中，那么最终得到的从栈底到栈头的次序字符串就是后缀表达式）

class Solution {
    
public:
    void cmp(stack<int> &nums, string op) {
    
        int a = nums.top(); nums.pop();
        int b = nums.top(); nums.pop();
        if(op == "+") nums.push(b+a);
        else if(op == "-") nums.push(b-a);
        else if(op == "*") nums.push(b*a);
        else nums.push(b/a);
    }
    int evalRPN(vector<string>& tokens) {
    
        stack<int> nums;
        for(string str: tokens) {
    
            if(str == "+" || str == "-" || str == "*" || str == "/") {
    
                cmp(nums,str);
            } else nums.push(stoi(str));
        }
        return nums.top();
    }
};

---

剑指 Offer II 037. 小行星碰撞

栈模拟，只有左边为正，右边为负才有可能发生碰撞。

class Solution {
    
public:
    vector<int> asteroidCollision(vector<int>& asteroids) {
    
        vector<int> stk;
        for(auto num: asteroids) {
    
            bool flag = true;
            while(flag && num < 0 && !stk.empty() && stk.back() > 0) {
    
                if(stk.back() > -num) flag = false;
                else if(stk.back() == -num) {
     //两都同时消失
                    stk.pop_back();
                    flag = false;
                } else stk.pop_back();
            }
            if(flag) stk.push_back(num);
        }
        return stk;
    }
};

---

剑指 Offer II 038. 每日温度

单调栈优化

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