大廠算法面試之leetcode精講17.棧
視頻講解（高效學(xué)習(xí)）:點(diǎn)擊學(xué)習(xí)
目錄：
Stack的特點(diǎn)：先進(jìn)后出（FILO）
使用場(chǎng)景：十進(jìn)制轉(zhuǎn)2進(jìn)制 函數(shù)調(diào)用堆棧
-
js里沒有棧，但是可以用數(shù)組模擬
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]
- 棧的時(shí)間復(fù)雜度：入棧和出棧
O(1)，查找O(n)
ds_24
20. 有效的括號(hào) (easy)
方法1.棧
ds_25
- 思路：首先如果字符串能組成有效的括號(hào)，則長度一定是偶數(shù)，我們可以遍歷字符串，遇到左括號(hào)則暫存，期待后面有右括號(hào)可以和它匹配，如果遇到右括號(hào)則檢查是否能和最晚暫存的做括號(hào)匹配。這就和棧這種數(shù)據(jù)結(jié)構(gòu)先進(jìn)后出的特性相吻合了。所以我們可以準(zhǔn)備一個(gè)棧存放括號(hào)對(duì)，遍歷字符串的時(shí)候，如果遇到左括號(hào)入棧，遇到右括號(hào)則判斷右括號(hào)是否能和棧頂元素匹配，在循環(huán)結(jié)束的時(shí)候還要判斷棧是否為空，如果不為空，則不是有效括號(hào)匹配的字符串
- 復(fù)雜度分析：時(shí)間復(fù)雜度
O(n)，空間復(fù)雜度O(n)，n為字符串的長度
js:
var isValid = function(s) {
const n = s.length;
if (n % 2 === 1) {//如果字符串能組成有效的括號(hào)，則長度一定是偶數(shù)
return false;
}
const pairs = new Map([//用棧存儲(chǔ)括號(hào)對(duì)
[')', '('],
[']', '['],
['}', '{']
]);
const stk = [];
for (let ch of s){//循環(huán)字符串
if (pairs.has(ch)) {
//遇到右括號(hào)則判斷右括號(hào)是否能和棧頂元素匹配
if (!stk.length || stk[stk.length - 1] !== pairs.get(ch)) {
return false;
}
stk.pop();
} else {
stk.push(ch);//如果遇到左括號(hào)入棧
}
};
return !stk.length;//循環(huán)結(jié)束的時(shí)候還要判斷棧是否為空
};
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. 用棧實(shí)現(xiàn)隊(duì)列 (easy)
方法1.棧
- 思路：這是一道模擬題，不涉及到具體算法，考察的就是對(duì)棧和隊(duì)列的掌握程度。使用棧來模式隊(duì)列的行為，如果僅僅用一個(gè)棧，是一定不行的，所以需要兩個(gè)棧一個(gè)輸入棧，一個(gè)輸出棧，這里要注意輸入棧和輸出棧的關(guān)系。在push數(shù)據(jù)的時(shí)候，只要數(shù)據(jù)放進(jìn)輸入棧就好，但在pop的時(shí)候，操作就復(fù)雜一些，輸出棧如果為空，就把進(jìn)棧數(shù)據(jù)全部導(dǎo)入進(jìn)來（注意是全部導(dǎo)入），再從出棧彈出數(shù)據(jù)，如果輸出棧不為空，則直接從出棧彈出數(shù)據(jù)就可以了。最后如果進(jìn)棧和出棧都為空的話，說明模擬的隊(duì)列為空了。
- 復(fù)雜度分析：push時(shí)間復(fù)雜度
O(1)，pop時(shí)間復(fù)雜度為O(n)，因?yàn)閜op的時(shí)候，輸出棧為空，則把輸入棧所有的元素加入輸出棧?？臻g復(fù)雜度O(n)，兩個(gè)棧空間
js:
var MyQueue = function() {
//準(zhǔn)備兩個(gè)棧
this.stack1 = [];
this.stack2 = [];
};
MyQueue.prototype.push = function(x) {//push的時(shí)候加入輸入棧
this.stack1.push(x);
};
MyQueue.prototype.pop = function() {
const size = this.stack2.length;
if(size) {//push的時(shí)候判斷輸出棧是否為空
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();//查看隊(duì)頭的元素 復(fù)用pop方法，然后在讓元素push進(jìn)輸出棧
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)
ds_145
- 思路：定義兩個(gè)棧stack和min_stack，stack正常push，min_stack只會(huì)push需要入棧和棧頂中較小的元素。getMin返回min_stack棧頂元素，top返回stack棧頂元素。
- 復(fù)雜度：所有操作的時(shí)間復(fù)雜度是
O(1)
js:
var MinStack = function () {
this.stack = [];
this.min_stack = [Infinity];
};
//stack正常push，min_stack只會(huì)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. 驗(yàn)證棧序列 （medium）
- 思路：用棧模擬出棧入棧的過程，當(dāng)popped中index指向的位置的元素和stack棧頂?shù)脑匾恢聲r(shí)，出棧 并且
index++，最后判斷stack是否為空 - 復(fù)雜度：時(shí)間復(fù)雜度
O(n)，pushed中的元素入棧出棧一次，空間復(fù)雜度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]);
//當(dāng)popped中index指向的位置的元素和stack棧頂?shù)脑匾恢聲r(shí)，出棧 并且 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. 兩數(shù)相加 II （medium）
ds_180
- 思路：將兩個(gè)鏈表的節(jié)點(diǎn)都推入棧中，然后不斷出棧，計(jì)算每個(gè)位置的值和進(jìn)位，串連成一個(gè)新的鏈表
- 復(fù)雜度：時(shí)間復(fù)雜度
O(max(m,n))，m，n是兩個(gè)鏈表的長度，空間復(fù)雜度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);//計(jì)算進(jìn)位
val = val % 10;//計(jì)算當(dāng)前節(jié)點(diǎn)的值
const curNode = new ListNode(val);
curNode.next = ansList;//向鏈表前插入新節(jié)點(diǎn)
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)
- 復(fù)雜度：時(shí)間復(fù)雜度
O(n)，空間復(fù)雜度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;
}
}
