大厂算法面试之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=021/2 21%2=110/2 10%2=05/2 5%2=12/2 2%2=01/2 1%2=1stack: [0,1,0,1,0,1]res: 1 0 1 0 1 0fn1(){ 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失常popMinStack.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; }}