LeetCode 總結(jié) - 搞定 Stack 面試題

[20] Valid Parentheses：判斷括號是否合法
[32] Longest Valid Parentheses：最長合法的括號
[232] Implement Queue using Stacks：用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
[225] Implement Stack using Queues：用兩個(gè)隊(duì)列實(shí)現(xiàn)棧
[155] Min Stack：最小棧
[150] Evaluate Reverse Polish Notation：逆波蘭表達(dá)式求值
[224] Basic Calculator：包含加減運(yùn)算的表達(dá)式計(jì)算
[71] Simplify Path：簡化Unix目錄路徑
[84] Largest Rectangle in Histogram：直方圖的最大面積
[16] Remove Duplicate Letters：去除重復(fù)字符
[《劍指offer》面試題22] 棧的壓入靖苇、彈出序列：判斷棧的壓棧、彈棧序列是否合法

[20] Valid Parentheses 合法的括號

https://leetcode.com/problems/valid-parentheses

問題：給定一個(gè)字符串耻陕，判斷括號匹配是否成立。

思路：

public boolean isValid(String s) {
    if (s == null || s.length() == 0) return true;
    Stack<Character> stack = new Stack<>();
    for (Character ch : s.toCharArray()) {
        if (ch == '(') {
            stack.push(')');
        } else if (ch == '[') {
            stack.push(']');
        } else if (ch == '{') {
            stack.push('}');
        } else {
            if (stack.empty() || stack.pop() != ch) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

參考講解：

https://www.youtube.com/watch?v=IeaAbOuKEBo

[32] Longest Valid Parentheses 最長合法的括號

https://leetcode.com/problems/longest-valid-parentheses

問題：

思路：

public int longestValidParentheses(String s) {
    // 存放每一個(gè)左括號的位置
    Stack<Integer> stack = new Stack<>();
    int res = 0;
    // 當(dāng)前括號組合的最左側(cè)邊界
    int start = -1;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            // 當(dāng)前括號組合為空
            if (stack.empty()) {
                start = i;
            } else {
                stack.pop();
                if (stack.empty()) {
                    res = Math.max(res, i - start);
                } else {
                    res = Math.max(res, i - stack.peek());
                }
            }
        }
    }
    return res;
}

參考講解：

https://www.youtube.com/watch?v=AqnGU4RjrxY
https://www.youtube.com/watch?v=M1Vw5Tk1rw4

[232] Implement Queue using Stacks

https://leetcode.com/problems/implement-queue-using-stacks

問題：

思路：

private Stack<Integer> stack1 = new Stack<>();
private Stack<Integer> stack2 = new Stack<>();

/**
 * 隊(duì)列的 push() 操作，就直接在 stack1 上進(jìn)行棧的 push() 操作即可
 */
public void push(int x) {
    stack1.push(x);
}

/**
 * 隊(duì)列的 pop() 操作加派，其實(shí)就是得到 stack1 中最底下的那個(gè)元素熟尉，怎么得到呢？先把上面逐個(gè)退出的元素一個(gè)個(gè)放在另一個(gè)棧 stack2 中熙卡；
 * 當(dāng) stack1 為空的時(shí)候杖刷，stack2 的棧頂元素，就是要取得的元素驳癌，用棧的 pop() 操作取出
 * 在將該元素進(jìn)行返回前滑燃，再將 stack2 中的元素倒回到 stack1 中，然后將該元素返回
 */
public int pop() {
    // 如果stack2為空
    if (stack2.isEmpty()) {
        // 且stack1不為空
        while (!stack1.isEmpty()) {
            // 則不斷把stack1中的元素pop出來表窘，并push到stack2中暫存
            stack2.push(stack1.pop());
        }
    }
    // stack2的棧頂元素其實(shí)就是stack1的棧底元素，我們要pop隊(duì)列的隊(duì)首元素其實(shí)也就是pop棧的棧底元素
    return stack2.pop();
}

public int peek() {
    if (stack2.isEmpty()) {
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
    }
    return stack2.peek();
}

public boolean empty() {
    return stack1.isEmpty() && stack2.isEmpty();
}

參考講解：

https://www.youtube.com/watch?v=h5BCSuzM3h4

[225] Implement Stack using Queues

https://leetcode.com/problems/implement-stack-using-queues

問題：

思路：

private Queue<Integer> queue = new LinkedList<>();

public void push(int x) {
    queue.offer(x);
    for (int i = 1; i < queue.size(); i++) {
        queue.add(queue.poll());
    }
}

public int pop() {
    return queue.poll();
}

public int top() {
    return queue.peek();
}

public boolean empty() {
    return queue.isEmpty();
}

參考講解：

https://www.youtube.com/watch?v=ZnyfAAdtOzY

[155] Min Stack

https://leetcode.com/problems/min-stack

問題：設(shè)計(jì)一個(gè)能返回棧中最小值的棧結(jié)構(gòu)黍匾。

思路：考慮使用另一個(gè)輔助棧填物，用來存儲(chǔ)[0..i]的最小值滞磺。

private LinkedList<Integer> list; // 存儲(chǔ)壓入棧中的所有值
private LinkedList<Integer> mins; // 存儲(chǔ)當(dāng)前棧中的最小值

public MinStack() {
    list = new LinkedList<Integer>();
    mins = new LinkedList<Integer>();
}

public void push(int x) {
    // 如果最小值棧中沒有值阅茶，或者當(dāng)前元素x比最小值棧中的最小值還要小，則把x放入最小值棧中
    if (mins.size() < 1 || mins.getLast() >= x) {
        mins.add(x);
    }
    list.add(x);

}

public void pop() {
    // pop 的時(shí)候，有可能 pop 出的是當(dāng)前棧中的最小值。因此在 pop 函數(shù)操作時(shí)，需同時(shí)操作維護(hù)最小值的 linkedlist
    if (list.getLast().equals(mins.getLast())) {
        mins.removeLast();
    }
    list.removeLast();
}

public int top() {
    return list.getLast();
}

public int getMin() {
    return mins.getLast();
}

Follow Up:
Q：如果還要加一個(gè)getMax()方法呢？
A：同樣用一個(gè)棧，但是入棧的判斷條件是大于等于棧頂鹿响。

參考講解：

https://www.youtube.com/watch?v=VvZPQzV8ppw

[150] Evaluate Reverse Polish Notation

https://leetcode.com/problems/evaluate-reverse-polish-notation

問題：逆波蘭表達(dá)式求值绸贡。

思路：只需要定義一個(gè)stack，如果是+, -, *, /四個(gè)運(yùn)算符，就取出棧頂?shù)膬蓚€(gè)數(shù)鸣峭，進(jìn)行相應(yīng)操作，之后將計(jì)算得到的結(jié)果壓入棧中拉岁；如果是數(shù)字，就直接入棧。最終stack只剩下一個(gè)元素狞尔，這個(gè)元素就是逆波蘭表達(dá)式的值丛版。

例如給定：["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

遇到4：stack : 4
遇到13：stack : 4 13
遇到5：stack : 4 13 5
遇到/號：pop : b=5, a=13 -> stack : 4 -> 13/5=2, push 2 to stack -> stack : 4 2
遇到+號：pop : b=2, a=4 -> stack : null -> 4+2=6, push 6 to stack -> stack : 6
pop剩下的一個(gè)元素6，得到計(jì)算結(jié)果為6

public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    for (String s : tokens) {
        if (s.equals("+")) {
            stack.push(stack.pop() + stack.pop());
        } else if (s.equals("-")) {
            int b = stack.pop();
            int a = stack.pop();
            stack.push(a - b);
        } else if (s.equals("*")) {
            stack.push(stack.pop() * stack.pop());
        } else if (s.equals("/")) {
            int b = stack.pop();
            int a = stack.pop();
            stack.push(a / b);
        } else {
            stack.push(Integer.parseInt(s));
        }
    }
    return stack.pop();
}

參考講解：

https://www.youtube.com/watch?v=yzoOG3jYLas

[224] Basic Calculator

https://leetcode.com/problems/basic-calculator

問題：

思路：題目中只有+ - ( )偏序。遍歷字符串页畦，對于每個(gè)字符c：

如果是數(shù)字，則一直遍歷到非數(shù)字字符研儒，把數(shù)字找出豫缨，并與結(jié)果相加
如果是+``-符號，將符號位sign設(shè)置成對應(yīng)的值
如果是(端朵，將res和sign壓入棧中州胳，重置res和sign
如果是)，將sign和res彈出棧逸月，并計(jì)算結(jié)果

例如給定：1 + 3 - (2 - 3)

遇到1：sign=1 -> res=0+1*1=1
遇到+：sign=1
遇到3：sign=1 -> res=1+3*1=4
遇到-：sign=-1
遇到(：push res(4), push sign(-1), res=0, sign=1 -> stack : 4 -1
遇到2：sign=1 -> res=0+2*1=2
遇到-：2-3相當(dāng)于2+(-3) -> sign=-1
遇到3：sign=-1 -> res=2+3*(-1)=-1
遇到)：res=-1*stack.pop()+stack.pop()=-1*(-1)+4=5

public int calculate(String s) {
    Stack<Integer> stack = new Stack<>();
    int sign = 1;
    int res = 0;
    for (int i = 0; i < s.length(); i++) {
        if (Character.isDigit(s.charAt(i))) {
            int num = s.charAt(i) - '0';
            // 如果下一個(gè)還是數(shù)字栓撞，就繼續(xù)計(jì)算
            while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
                int next = s.charAt(i + 1) - '0';
                num = num * 10 + next;
                i++;
            }
            res += num * sign;
        } else if (s.charAt(i) == '+') {
            sign = 1;
        } else if (s.charAt(i) == '-') {
            sign = -1;
        } else if (s.charAt(i) == '(') {
            stack.push(res);
            stack.push(sign);
            res = 0;
            sign = 1;
        } else if (s.charAt(i) == ')') {
            res = res * stack.pop() + stack.pop();
        }
    }
    return res;
}

參考講解：

https://www.youtube.com/watch?v=ijyUwyt5vkU

[71] Simplify Path

https://leetcode.com/problems/simplify-path

問題：解析linux路徑，有”.”表示不變和”..”表示回上層碗硬。

思路：

public String simplifyPath(String path) {
    Stack<String> stack = new Stack<>();
    String[] paths = path.split("/+");
    for (String s : paths) {
        if (s.equals("..")) {
            if (!stack.isEmpty()) {
                stack.pop();
            }
        } else if (!s.equals(".") && !s.equals("")) {
            stack.push(s);
        }
    }
    String res = "";
    while (!stack.isEmpty()) {
        res = "/" + stack.pop() + res;
    }
    if (res.length() == 0) return "/";
    return res;
}

參考講解：

https://www.youtube.com/watch?v=u5KBpcCP-G0
https://www.youtube.com/watch?v=l-og2X5GibY

[84] Largest Rectangle in Histogram

https://leetcode.com/problems/largest-rectangle-in-histogram

問題：

思路：

參考講解：

https://www.youtube.com/watch?v=TH9UaZ6JGcA

[16] Remove Duplicate Letters

https://leetcode.com/problems/remove-duplicate-letters

問題：

思路：如果一個(gè)字母c瓤湘，小于前面的某個(gè)字母b，并且b在a后面還有恩尾，那么b應(yīng)當(dāng)被刪除弛说。
用棧來實(shí)現(xiàn)。

遍歷一遍統(tǒng)計(jì)每個(gè)字母出現(xiàn)次數(shù)翰意。
再遍歷一遍木人，對當(dāng)前字母c的統(tǒng)計(jì)數(shù)字減一。
如果c不在棧中冀偶，則進(jìn)行如下棧操作：
1. 如果當(dāng)前字母c小于棧頂醒第，并且棧頂元素還有剩余，則出棧棧頂进鸠，并標(biāo)記棧頂不在棧中稠曼。重復(fù)該操作直到棧頂元素不滿足要求或者棧為空。
2. 入棧字母c客年，并標(biāo)記c已經(jīng)在棧中霞幅。

public String removeDuplicateLetters(String s) {
    int[] cnt = new int[26];
    boolean[] inStack = new boolean[26];
    char[] st = new char[s.length()];
    int len = 0;
    for (char c : s.toCharArray()) {
        cnt[c - 'a']++;
    }
    for (char c : s.toCharArray()) {
        cnt[c - 'a']--;
        
        if (!inStack[c - 'a']) {
            while (len > 0 && c < st[len - 1] && cnt[st[len - 1] - 'a'] > 0) {
                inStack[st[--len] - 'a'] = false;
            }
            
            st[len++] = c;
            inStack[c - 'a'] = true;
        }
    }
    return new String(st, 0, len);
}

public String removeDuplicateLetters(String s) {
    if (s == null || s.length() == 0) return s;
    Map<Character, Integer> map = new HashMap<>();
    for (int i = 0; i < s.length(); i++) map.put(s.charAt(i), i);
    char[] res = new char[map.size()];
    int start = 0;
    int end = findMinLastPos(map);
    for (int i = 0; i < res.length; i++) {
        char minChar = 'z' + 1;
        for (int k = start; k <= end; k++) {
            if (map.containsKey(s.charAt(k)) && s.charAt(k) < minChar) {
                minChar = s.charAt(k);
                start = k + 1;
            }
        }
        res[i] = minChar;
        map.remove(minChar);
        if (s.charAt(end) == minChar) {
            end = findMinLastPos(map);
        }
    }
    return new String(res);
}

private int findMinLastPos(Map<Character, Integer> map) {
    int res = Integer.MAX_VALUE;
    for (int num : map.values()) {
        res = Math.min(res, num);
    }
    return res;
}

參考講解：

https://www.youtube.com/watch?v=0UlVGdQG1_Q

[《劍指offer》面試題22] 棧的壓入、彈出序列

https://www.nowcoder.com/questionTerminal/d77d11405cc7470d82554cb392585106

問題：已知壓棧序列量瓜，判斷合法的彈出序列司恳。輸入兩個(gè)整數(shù)序列，第一個(gè)序列表示棧的壓入順序绍傲，請判斷第二個(gè)序列是否為該棧的彈出順序扔傅。假設(shè)壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序，序列4铅鲤，5,3,2,1是該壓棧序列對應(yīng)的一個(gè)彈出序列划提，但4,3,5,1,2就不可能是該壓棧序列的彈出序列。

思路：借用一個(gè)輔助的棧邢享，遍歷壓棧順序鹏往，先講第一個(gè)放入棧中输枯，這里是1絮姆，然后判斷棧頂元素是不是出棧順序的第一個(gè)元素，這里是4扣唱，很顯然1≠4款违，所以我們繼續(xù)壓棧唐瀑，直到相等以后開始出棧，出棧一個(gè)元素插爹，則將出棧順序向后移動(dòng)一位哄辣，直到不相等，這樣循環(huán)等壓棧順序遍歷完成赠尾，如果輔助棧還不為空力穗，說明彈出序列不是該棧的彈出順序。

舉例：入棧序列1,2,3,4,5气嫁，出棧序列4,5,3,2,1

首先1入輔助棧当窗，此時(shí)棧頂1≠4，繼續(xù)入棧2
此時(shí)棧頂2≠4寸宵，繼續(xù)入棧3
此時(shí)棧頂3≠4崖面，繼續(xù)入棧4
此時(shí)棧頂4＝4，出棧4梯影，彈出序列向后一位巫员，此時(shí)為5，,輔助棧里面是1,2,3
此時(shí)棧頂3≠5光酣，繼續(xù)入棧5
此時(shí)棧頂5=5疏遏，出棧5,彈出序列向后一位，此時(shí)為3救军，,輔助棧里面是1,2,3
...依次執(zhí)行，最后輔助棧為空倘零。如果不為空說明彈出序列不是該棧的彈出順序唱遭。

public boolean isPopOrder(int[] pushA, int[] popA) {
    if (pushA.length == 0) return false;
    Stack<Integer> stack = new Stack<>();
    // 用于標(biāo)識彈出序列的位置
    int popIndex = 0;
    for (int i = 0; i < pushA.length; ) {
        stack.push(pushA[i++]);
        // 如果棧不為空，且棧頂元素等于彈出序列
        while (popIndex < popA.length && stack.peek() == popA[popIndex]) {
            stack.pop();
            // 彈出序列向后一位
            popIndex++;
        }
    }
    return stack.empty();
}