【算法】Java 中栈的使用

  栈是一种重要的数据结构，满足后进先出，是面试中会重点考察的内容。下面通过例题来学习栈的使用。

1.力扣20.有效的括号^[1]

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。

示例 1：   输入：s = “()”   输出：true

示例 2：   输入：s = “()[]{}”   输出：true

示例 3：   输入：s = “(]”   输出：false

括号匹配的过程中，后遇到的左括号要先匹配，满足后进先出，因此可以用栈来解决。

public boolean isValid(String s) {
          
   
    Deque<Character> stack = new LinkedList<>();
    for (char c : s.toCharArray()) {
          
   
        if (c == () stack.push());
        else if (c == [) stack.push(]);
        else if (c == {) stack.push(});
        else {
          
   
            if (stack.isEmpty() || c != stack.pop()) return false;
        }
    }
    return stack.isEmpty();
}

2.力扣32. 最长有效括号^[2]

给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：   输入：s = “(()”   输出：2   解释：最长有效括号子串是 “()”

示例 2：   输入：s = “)()())”   输出：4   解释：最长有效括号子串是 “()()”

示例 3：   输入：s = “”   输出：0

和上一题类似，后遇到的左括号要先匹配，满足后进先出，因此可以用栈来解决。不同的是本题要找最大的可以匹配的长度，因此可以将 push 的对象从括号换成下标便于计算长度。

public int longestValidParentheses(String s) {
          
   
    int ans = 0;
    LinkedList<Integer> stack = new LinkedList<>();
    // 初始化放入 -1，第一次匹配时使用
    // 例如"()"，那么右括号下标是 1，1-(-1)=2
    // 因此栈中的数字表示上一个没有匹配的坐标，例如最开始没有匹配的坐标是-1
    stack.push(-1);
    for (int i = 0; i < s.length(); i++) {
          
   
        if (s.charAt(i) == () {
          
   
            stack.push(i);	// 将右括号的下标放入队列
        } else {
          
   	// 遇到右括号
            stack.pop();	// 弹出一个左括号与之进行匹配，下面讨论是否匹配
            if (stack.isEmpty()) {
          
   	// 为空说明没有匹配，因为栈中的数字表示上一个没有匹配的坐标，却全部被弹出了
                stack.push(i);	// 不匹配之后将新的不匹配的下标入栈，作为新的起点
            } else {
          
   	// 不为空才是真正匹配了
                ans = Math.max(ans, i - stack.peek());	// 更新答案
            }
        }
    }
    return ans;
}

Reference

[1]力扣20.有效的括号：https://leetcode-cn.com/problems/valid-parentheses

[2]力扣32. 最长有效括号：https://leetcode-cn.com/problems/longest-valid-parentheses