关于leetcode个人解题总结:大厂算法面试之leetcode精讲17栈

大厂算法面试之 leetcode 精讲 17. 栈

视频解说（高效学习）: 点击学习

目录：

1. 开篇介绍

2. 工夫空间复杂度

3. 动静布局

4. 贪婪

5. 二分查找

6. 深度优先 & 广度优先

7. 双指针

8. 滑动窗口

9. 位运算

10. 递归 & 分治

11 剪枝 & 回溯

12. 堆

13. 枯燥栈

14. 排序算法

15. 链表

16.set&map

17. 栈

18. 队列

19. 数组

20. 字符串

21. 树

22. 字典树

23. 并查集

24. 其余类型题

• Stack 的特点：先进后出（FILO）
• 应用场景：十进制转 2 进制 函数调用堆栈

• js 里没有栈，然而能够用数组模仿

  42/2 42%2=0
  21/2 21%2=1
  10/2 10%2=0
  5/2   5%2=1
  2/2   2%2=0
  1/2   1%2=1
  stack: [0,1,0,1,0,1]
  res:    1 0 1 0 1 0
  
  fn1(){fn2()
  }
  fn2(){fn3()
    }
  fn3(){}
  fn1()
  
  stack:[fn1,fn2,fn3]

• 栈的工夫复杂度：入栈和出栈O(1)，查找O(n)

20. 无效的括号 (easy)

办法 1. 栈

• 思路：首先如果字符串能组成无效的括号，则长度肯定是偶数，咱们能够遍历字符串，遇到左括号则暂存，期待前面有右括号能够和它匹配，如果遇到右括号则查看是否能和最晚暂存的做括号匹配。这就和栈这种数据结构先进后出的个性相吻合了。所以咱们能够筹备一个栈寄存括号对，遍历字符串的时候，如果遇到左括号入栈，遇到右括号则判断右括号是否能和栈顶元素匹配，在循环完结的时候还要判断栈是否为空，如果不为空，则不是无效括号匹配的字符串
• 复杂度剖析：工夫复杂度O(n)，空间复杂度O(n)，n 为字符串的长度

js:

var isValid = function(s) {
    const n = s.length;
    if (n % 2 === 1) {// 如果字符串能组成无效的括号，则长度肯定是偶数
        return false;
    }
    const pairs = new Map([// 用栈存储括号对
        [')', '('],
        [']', '['],
        ['}', '{']
    ]);
    const stk = [];
    for (let ch of s){// 循环字符串
        if (pairs.has(ch)) {
              // 遇到右括号则判断右括号是否能和栈顶元素匹配
            if (!stk.length || stk[stk.length - 1] !== pairs.get(ch)) {return false;}
            stk.pop();} else {stk.push(ch);// 如果遇到左括号入栈
        }
    };
    return !stk.length;// 循环完结的时候还要判断栈是否为空
};

Java:

class Solution {public boolean isValid(String s) {int n = s.length();
        if (n % 2 == 1) {return false;}

        Map<Character, Character> pairs = new HashMap<Character, Character>() {{put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();
        for (int i = 0; i < n; i++) {char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {return false;}
                stack.pop();} else {stack.push(ch);
            }
        }
        return stack.isEmpty();}
}

232. 用栈实现队列 (easy)

办法 1. 栈

动画过大，点击查看

• 思路：这是一道模拟题，不波及到具体算法，考查的就是对栈和队列的把握水平。应用栈来模式队列的行为，如果仅仅用一个栈，是肯定不行的，所以须要两个栈 一个输出栈，一个输入栈，这里要留神输出栈和输入栈的关系。在 push 数据的时候，只有数据放进输出栈就好，但在 pop 的时候，操作就简单一些，输入栈如果为空，就把进栈数据全副导入进来（留神是全副导入），再从出栈弹出数据，如果输入栈不为空，则间接从出栈弹出数据就能够了。最初如果进栈和出栈都为空的话，阐明模仿的队列为空了。
• 复杂度剖析：push 工夫复杂度O(1)，pop 工夫复杂度为O(n)，因为 pop 的时候，输入栈为空，则把输出栈所有的元素退出输入栈。空间复杂度O(n)，两个栈空间

js:

var MyQueue = function() {
  // 筹备两个栈
   this.stack1 = [];
   this.stack2 = [];};

MyQueue.prototype.push = function(x) {//push 的时候退出输出栈
   this.stack1.push(x);
};

MyQueue.prototype.pop = function() {
   const size = this.stack2.length;
   if(size) {//push 的时候判断输入栈是否为空
       return this.stack2.pop();// 不为空则输入栈出栈}
   while(this.stack1.length) {// 输入栈为空，则把输出栈所有的元素退出输入栈
       this.stack2.push(this.stack1.pop());
   }
   return this.stack2.pop();};

MyQueue.prototype.peek = function() {const x = this.pop();// 查看队头的元素 复用 pop 办法，而后在让元素 push 进输入栈
   this.stack2.push(x);
   return x;
};

MyQueue.prototype.empty = function() {return !this.stack1.length && !this.stack2.length};

Java:

class MyQueue {

    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public MyQueue() {stack1 = new Stack<>();
        stack2 = new Stack<>();}
    
    public void push(int x) {stack1.push(x);
    }
    
    public int pop() {dumpStack1();
        return stack2.pop();}
    
    public int peek() {dumpStack1();
        return stack2.peek();}
    
    public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}

    private void dumpStack1(){if (stack2.isEmpty()){while (!stack1.isEmpty()){stack2.push(stack1.pop());
            }
        }
    }
}

155. 最小栈 (easy)

• 思路：定义两个栈 stack 和 min_stack，stack 失常 push，min_stack 只会 push 须要入栈和栈顶中较小的元素。getMin 返回 min_stack 栈顶元素，top 返回 stack 栈顶元素。
• 复杂度：所有操作的工夫复杂度是O(1)

js:

var MinStack = function () {this.stack = [];
    this.min_stack = [Infinity];
};

//stack 失常 push，min_stack 只会 push 须要入栈和栈顶中较小的元素
MinStack.prototype.push = function (x) {this.stack.push(x);
    this.min_stack.push(Math.min(this.min_stack[this.min_stack.length - 1], x));
};

//stack 失常 pop，min_stack 失常 pop
MinStack.prototype.pop = function () {this.stack.pop();
    this.min_stack.pop();};

// 返回 stack 栈顶元素
MinStack.prototype.top = function () {return this.stack[this.stack.length - 1];
};

// 返回 min_stack 栈顶元素
MinStack.prototype.getMin = function () {return this.min_stack[this.min_stack.length - 1];
};

java:

class MinStack {
  Deque<Integer> stack;
  Deque<Integer> minStack;

  public MinStack() {stack = new LinkedList<Integer>();
      minStack = new LinkedList<Integer>();
      minStack.push(Integer.MAX_VALUE);
  }
  
  public void push(int x) {stack.push(x);
      minStack.push(Math.min(minStack.peek(), x));
  }
  
  public void pop() {stack.pop();
      minStack.pop();}
  
  public int top() {return stack.peek();
  }
  
  public int getMin() {return minStack.peek();
  }
}

946. 验证栈序列（medium）

动画过大，点击查看

• 思路：用栈模拟出栈入栈的过程，当 popped 中 index 指向的地位的元素和 stack 栈顶的元素统一时，出栈 并且 index++，最初判断 stack 是否为空
• 复杂度：工夫复杂度O(n)，pushed 中的元素入栈出栈一次，空间复杂度O(n)，栈的大小

js：

const validateStackSequences = (pushed, popped) => {const stack = [];// 用栈模拟出栈入栈的过程
    let index = 0;
    const len = pushed.length;
    for (let i = 0; i < len; i++) {stack.push(pushed[i]);
          // 当 popped 中 index 指向的地位的元素和 stack 栈顶的元素统一时，出栈 并且 index++
        while (popped[index] !== undefined && popped[index] === stack[stack.length - 1]) {stack.pop();
            index++;
        }
    }
    return !stack.length;// 最初判断 stack 是否为空
};

java:

class Solution {public boolean validateStackSequences(int[] pushed, int[] popped) {if(pushed == null){return true;}
        Stack<Integer> stack = new Stack<>();
        int index = 0;
        for(int i=0;i<pushed.length;i++){stack.push(pushed[i]);
            while(!stack.isEmpty() && index < popped.length && popped[index] == stack.peek()){int pop = stack.pop();
                index++;
            }
        }
        return stack.isEmpty();}
}

445. 两数相加 II（medium）

• 思路：将两个链表的节点都推入栈中，而后一直出栈，计算每个地位的值和进位，串连成一个新的链表
• 复杂度：工夫复杂度O(max(m,n))，m，n 是两个链表的长度，空间复杂度O(m+n)

js：

var addTwoNumbers = function(l1, l2) {const stack1 = [];
    const stack2 = [];
    while (l1 || l2) {// 两链表入栈
        if (l1) {stack1.push(l1.val);
            l1 = l1.next;
        }
        if (l2) {stack2.push(l2.val);
            l2 = l2.next;
        }
    }
    let carry = 0;
    let ansList = null;
    while (stack1.length || stack2.length || carry !== 0) {// 一直出栈
        const s1 = stack1.length ? stack1.pop() : 0;
        const s2 = stack2.length ? stack2.pop() : 0;
        let val = s1 + s2 + carry;
        carry = parseInt(val / 10);// 计算进位
        val = val % 10;// 计算以后节点的值
        const curNode = new ListNode(val);
        curNode.next = ansList;// 向链表前插入新节点
        ansList = curNode;// 从新赋值 ansList
    }
    return ansList;
};

java：

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {Deque<Integer> stack1 = new LinkedList<Integer>();
        Deque<Integer> stack2 = new LinkedList<Integer>();
        while (l1 != null) {stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {stack2.push(l2.val);
            l2 = l2.next;
        }
        int carry = 0;
        ListNode ansList = null;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {int s1 = stack1.isEmpty() ? 0 : stack1.pop();
            int s2 = stack2.isEmpty() ? 0 : stack2.pop();
            int val = s1 + s2 + carry;
            carry = val / 10;
            val %= 10;
            ListNode curNode = new ListNode(val);
            curNode.next = ansList;
            ansList = curNode;
        }
        return ansList;
    }
}

682. 棒球较量 (easy)

• 复杂度：工夫复杂度O(n)，空间复杂度O(n)

js：

let calPoints = function(ops) {let res = [];
    for(let i = 0; i < ops.length; i++){switch(ops[i]){
            case "C":
                res.pop();
                break;
            case "D":
                res.push(+res[res.length - 1] * 2);
                break;
            case "+":
                res.push(+res[res.length - 1] + +res[res.length - 2]);
                break;
            default:
                res.push(+ops[i]);
        }
    }
    return res.reduce((i, j) => i + j);
};

java：

class Solution {public int calPoints(String[] ops) {Stack<Integer> stack = new Stack();

        for(String op : ops) {if (op.equals("+")) {int top = stack.pop();
                int newtop = top + stack.peek();
                stack.push(top);
                stack.push(newtop);
            } else if (op.equals("C")) {stack.pop();
            } else if (op.equals("D")) {stack.push(2 * stack.peek());
            } else {stack.push(Integer.valueOf(op));
            }
        }

        int ans = 0;
        for(int score : stack) ans += score;
        return ans;
    }
}