LeetCode 总结 - 搞定 Stack 面试题

[20] Valid Parentheses 合法的括号

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

问题：给定一个字符串，判断括号匹配是否成立。

思路：

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();
}

参考讲解：

[32] Longest Valid Parentheses 最长合法的括号

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

问题：

思路：

public int longestValidParentheses(String s) {
    // 存放每一个左括号的位置
    Stack<Integer> stack = new Stack<>();
    int res = 0;
    // 当前括号组合的最左侧边界
    int start = -1;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            // 当前括号组合为空
            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;
}

参考讲解：

[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<>();

/**
 * 队列的 push() 操作，就直接在 stack1 上进行栈的 push() 操作即可
 */
public void push(int x) {
    stack1.push(x);
}

/**
 * 队列的 pop() 操作，其实就是得到 stack1 中最底下的那个元素，怎么得到呢？先把上面逐个退出的元素一个个放在另一个栈 stack2 中；
 * 当 stack1 为空的时候，stack2 的栈顶元素，就是要取得的元素，用栈的 pop() 操作取出
 * 在将该元素进行返回前，再将 stack2 中的元素倒回到 stack1 中，然后将该元素返回
 */
public int pop() {
    // 如果stack2为空
    if (stack2.isEmpty()) {
        // 且stack1不为空
        while (!stack1.isEmpty()) {
            // 则不断把stack1中的元素pop出来，并push到stack2中暂存
            stack2.push(stack1.pop());
        }
    }
    // stack2的栈顶元素其实就是stack1的栈底元素，我们要pop队列的队首元素其实也就是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();
}

参考讲解：

[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();
}

参考讲解：

[155] Min Stack

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

问题：设计一个能返回栈中最小值的栈结构。

思路：考虑使用另一个辅助栈，用来存储[0..i]的最小值。

private LinkedList<Integer> list; // 存储压入栈中的所有值
private LinkedList<Integer> mins; // 存储当前栈中的最小值

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

public void push(int x) {
    // 如果最小值栈中没有值，或者当前元素x比最小值栈中的最小值还要小，则把x放入最小值栈中
    if (mins.size() < 1 || mins.getLast() >= x) {
        mins.add(x);
    }
    list.add(x);

}

public void pop() {
    // pop 的时候，有可能 pop 出的是当前栈中的最小值。因此在 pop 函数操作时，需同时操作维护最小值的 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：如果还要加一个getMax()方法呢？
A：同样用一个栈，但是入栈的判断条件是大于等于栈顶。

参考讲解：

[150] Evaluate Reverse Polish Notation

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

问题：逆波兰表达式求值。

思路：只需要定义一个stack，如果是+, -, *, /四个运算符，就取出栈顶的两个数，进行相应操作，之后将计算得到的结果压入栈中；如果是数字，就直接入栈。最终stack只剩下一个元素，这个元素就是逆波兰表达式的值。

例如给定：["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剩下的一个元素6，得到计算结果为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();
}

参考讲解：

[224] Basic Calculator

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

问题：

思路：题目中只有+ - ( )。遍历字符串，对于每个字符c：

  • 如果是数字，则一直遍历到非数字字符，把数字找出，并与结果相加
  • 如果是+``-符号，将符号位sign设置成对应的值
  • 如果是(，将res和sign压入栈中，重置res和sign
  • 如果是)，将sign和res弹出栈，并计算结果

例如给定：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相当于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';
            // 如果下一个还是数字，就继续计算
            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;
}

参考讲解：

[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;
}

参考讲解：

[84] Largest Rectangle in Histogram

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

问题：

思路：

参考讲解：

[16] Remove Duplicate Letters

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

问题：

思路：如果一个字母c，小于前面的某个字母b，并且b在a后面还有，那么b应当被删除。
用栈来实现。

  1. 遍历一遍统计每个字母出现次数。
  2. 再遍历一遍，对当前字母c的统计数字减一。
  3. 如果c不在栈中，则进行如下栈操作：
    1. 如果当前字母c小于栈顶，并且栈顶元素还有剩余，则出栈栈顶，并标记栈顶不在栈中。重复该操作直到栈顶元素不满足要求或者栈为空。
    2. 入栈字母c，并标记c已经在栈中。
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;
}

参考讲解：

[《剑指offer》面试题22] 栈的压入、弹出序列

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

问题：已知压栈序列，判断合法的弹出序列。输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

思路：借用一个辅助的栈，遍历压栈顺序，先讲第一个放入栈中，这里是1，然后判断栈顶元素是不是出栈顺序的第一个元素，这里是4，很显然1≠4，所以我们继续压栈，直到相等以后开始出栈，出栈一个元素，则将出栈顺序向后移动一位，直到不相等，这样循环等压栈顺序遍历完成，如果辅助栈还不为空，说明弹出序列不是该栈的弹出顺序。

举例：入栈序列1,2,3,4,5，出栈序列4,5,3,2,1

  • 首先1入辅助栈，此时栈顶1≠4，继续入栈2
  • 此时栈顶2≠4，继续入栈3
  • 此时栈顶3≠4，继续入栈4
  • 此时栈顶4＝4，出栈4，弹出序列向后一位，此时为5，,辅助栈里面是1,2,3
  • 此时栈顶3≠5，继续入栈5
  • 此时栈顶5=5，出栈5,弹出序列向后一位，此时为3，,辅助栈里面是1,2,3
  • ...依次执行，最后辅助栈为空。如果不为空说明弹出序列不是该栈的弹出顺序。
public boolean isPopOrder(int[] pushA, int[] popA) {
    if (pushA.length == 0) return false;
    Stack<Integer> stack = new Stack<>();
    // 用于标识弹出序列的位置
    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();
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 216,142评论 6赞 498
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,298评论 3赞 392
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 162,068评论 0赞 351
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,081评论 1赞 291
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,099评论 6赞 388
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,071评论 1赞 295
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,990评论 3赞 417
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,832评论 0赞 273
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,274评论 1赞 310
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,488评论 2赞 331
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,649评论 1赞 347
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,378评论 5赞 343
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,979评论 3赞 325
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,625评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,796评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,643评论 2赞 368
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,545评论 2赞 352