Algo_4_Stack

code c++ algo

學習算法

Leetcode 150

  • 判斷是否為符號，不是存stack，否則做運算
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<string> st;
        for(auto t : tokens){
            if(t != "+" && t != "-" && t != "*" && t != "/"){
                st.push(t);
            }else {
                int a = stoi(st.top());
                st.pop();
                int b = stoi(st.top());
                st.pop();
                if(t == "+"){
                    int c = b + a;
                    st.push(to_string(c));
                }else if(t == "-"){
                    int c = b - a;
                    st.push(to_string(c));
                }else if(t == "*"){
                    int c = b * a;
                    st.push(to_string(c));
                }else if(t == "/"){
                    int c = b / a;
                    st.push(to_string(c));
                }
            }
        }
        return stoi(st.top());
    }
};

Leetcode 739

  • stack存index位置，找到大於的話，就把大於元素的index和當前最大得idx做運算
  • 因為有在vector設初始值0，所以都沒有大於元素後會自動為0
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> st;
        vector<int> vc(temperatures.size(),0);
        for(int i=0;i<temperatures.size();i++){
            while(!st.empty() && temperatures[i] > temperatures[st.top()]){
                int idx = st.top();
                st.pop();
                vc[idx] = i-idx;
            }
            st.push(i);
        }
        return vc;
    }
};

Leetcode 155

方法1

  • 使用vector<pair<int,int>來代替stack
  • pair的first存當前元素，second存之前的最小值
class MinStack {
private:
    vector<pair<int,int>> st;
public:
    MinStack() {
        
    }
    
    void push(int val) {
        if(st.empty()){
            st.push_back({val,val});
        }else{
            st.push_back({val,min(val,st.back().second)});
        }
    }
    
    void pop() {
        st.pop_back();
    }
    
    int top() {
        return st.back().first;
    }
    
    int getMin() {
        return st.back().second;
    }
};

方法2

  • 使用雙stack
  • data 這個stack來存放任何值
  • minStack存放比當前top元素小的值，保持最小元素在頂端
  • 當minStack的頂端元素比data接收到的元素小的時候，重新push自己的top以維護top永遠為最小
class MinStack {
private:
    stack<int> data;
    stack<int> minstack;
public:
    MinStack() {
        
    }
    
    void push(int val) {
        data.push(val);
        if(minstack.empty() || val < minstack.top()){
            minstack.push(val);
        }else{
            minstack.push(minstack.top());
        }
    }
    
    void pop() {
        data.pop();
        minstack.pop();
    }
    
    int top() {
        return data.top();
    }
    
    int getMin() {
        return minstack.top();
    }
};
 
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

Leetcode 921

  • 因為只有( 能和 )結合，因此判斷(就好，如果可以的話就pop出stack，不行則push
class Solution {
public:
    int minAddToMakeValid(string s) {
        stack<char> st;
        int count = 0;
        for(char str : s) {
            if(st.empty()){
                st.push(str);
            }else if(st.top() == '(' && str == ')'){
                st.pop();
            }else{
                st.push(str);
            }
        }
        return st.size();
    }
};