棧適合解決匹配類問(wèn)題

我們?cè)趧h除相鄰重復(fù)項(xiàng)的時(shí)候，其實(shí)就是要知道當(dāng)前遍歷的這個(gè)元素，我們?cè)谇耙晃皇遣皇潜闅v過(guò)一樣數(shù)值的元素，那么如何記錄前面遍歷過(guò)的元素呢？

所以就是用棧來(lái)存放，那么棧的目的，就是存放遍歷過(guò)的元素，當(dāng)遍歷當(dāng)前的這個(gè)元素的時(shí)候，去棧里看一下我們是不是遍歷過(guò)相同數(shù)值的相鄰元素，然后再去做對(duì)應(yīng)的消除操作。

有效的括號(hào)

力扣題目
考點(diǎn)：棧(對(duì)稱匹配類的題目)
思路：遍歷這個(gè)字符串，當(dāng)棧為空或者棧頂元素和遍歷元素不相等的話，則把遍歷元素添加到棧中，如果棧頂元素=遍歷元素，則pop掉棧頂元素。
代碼：
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)

var isValid = function(s) {
    //若為單數(shù)，直接返回false
    if(s.length % 2 !==0) return false
    let stack=[]
    for(let i=0;i<s.length;i++){
        if(s[i] === '(' || s[i] === '[' ||s[i] === '{' ){
            stack.push(s[i])
            continue
        }
        if((s[i]===')' && '('=== stack[stack.length-1]) ||( s[i]===']' && '['=== stack[stack.length-1] )||(s[i]==='}' && '{'=== stack[stack.length-1])){
            stack.pop()
        }else{
            return false
        }
    }
    return stack.length === 0
};

刪除字符串中的所有相鄰重復(fù)項(xiàng)

力扣題目

考點(diǎn)：棧（匹配問(wèn)題）
代碼：
時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度:O(n)

var removeDuplicates = function(s) {
    let stack=[]
    for(let i=0;i<s.length;i++){
        // 相同就彈出，
        // 不同就壓棧
        if(stack[stack.length-1] === s[i]){
            stack.pop()
            continue
        }
        stack.push(s[i])
    }
    return stack.join('')
};

逆波蘭表達(dá)式求值

力扣題目

注意：

1. 數(shù)字做運(yùn)算的順序
2. 遇到除號(hào)；結(jié)果小于0時(shí)，向上取整，；結(jié)果大于0時(shí)，向下取整
3. 遇到減號(hào)，且被減數(shù)小于零，即2--3的情況；將符號(hào)轉(zhuǎn)換為正號(hào)進(jìn)行運(yùn)算

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)

var evalRPN = function(tokens) {
   //遇到數(shù)字放進(jìn)去
   //遇到符號(hào)，出棧兩個(gè)數(shù)字；再把結(jié)果放進(jìn)去
   let stack=[]
   let sign= '+-*/'
    let res =0

   for(let i in tokens){
       if(sign.includes(tokens[i])){
           let n1=stack.pop()
           let n2=stack.pop()

           if(tokens[i] ==='/'){ //若為除法，特殊處理
               res = ((n2)/(n1)) < 0? Math.ceil((n2)/(n1)): Math.floor((n2)/(n1))
           }else if(tokens[i] ==='-' && n1<0){ //若出現(xiàn)類似2--3的情況，特殊處理
               res= eval(n2+'+'+Math.abs(n1))
           }else{
             res = eval((n2)+tokens[i]+(n1))
           }
            stack.push(res)
           continue
       }
       stack.push(tokens[i])
   }
   return Number(stack[0])
};

參考：
感覺(jué)參考的代碼更優(yōu)雅:
入棧時(shí)，直接放入數(shù)字類型；求除數(shù)那里利用了按位或運(yùn)算，簡(jiǎn)化寫法：

n1 / n2 | 0

var evalRPN = function (tokens) {
    const stack = [];
    for (const token of tokens) {
        if (isNaN(Number(token))) { // 非數(shù)字
            const n2 = stack.pop(); // 出棧兩個(gè)數(shù)字
            const n1 = stack.pop();
            switch (token) { // 判斷運(yùn)算符類型，算出新數(shù)入棧
                case "+":
                    stack.push(n1 + n2);
                    break;
                case "-":
                    stack.push(n1 - n2);
                    break;
                case "*":
                    stack.push(n1 * n2);
                    break;
                case "/":
                    stack.push(n1 / n2 | 0);
                    break;
            }
        } else { // 數(shù)字
            stack.push(Number(token));
        }
    }
    return stack[0]; // 因沒(méi)有遇到運(yùn)算符而待在棧中的結(jié)果
};