最长有效括号

前言

最近被新型冠状病毒搞得人心惶惶，大家都不太敢出门，我也不敢出门（哈哈哈），索性就在家里刷了一道leetcode的简单题——有效的括号（leetcode20题），说简单也不简单，说难也不难，刷完之后觉得意犹未尽。然后再刷了一道leetcode的困难题——最长有效括号（leetcode32题）。今天就来讲一下这两道相似题目的题解。

第一题（leetcode20_有效的括号）

思路

先列出括号的类型把他存在HashMap中，然后利用栈先进后出的特性来解决。如果是左括号就直接进栈，如果是右括号就出栈，然后判断出栈的左括号是否对应着对应的右括号即可。

代码

package leetcode;

import java.util.HashMap;
import java.util.Stack;

/**
 * @author god-jiang
 * @date 2020/1/30  11:01
 */
public class StackIsValid {

    public static boolean isValid(String s) {
        //把括号的类型存进HashMap中
        HashMap<Character,Character> map=new HashMap<>();
        map.put(')','(');
        map.put('}','{');
        map.put(']','[');
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            //如果是左括号，直接进栈
            if (!map.containsKey(s.charAt(i))) {
                stack.push(s.charAt(i));
            } else {
                //如果是右括号，出栈然后判断出栈左括号对应HashMap的左括号是否一致
                char top = stack.isEmpty() ? '#' : stack.pop();
                if (top != map.get(s.charAt(i))) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

复杂度分析

• 时间复杂度：O(N)。因为整个过程遍历一遍就可以处理完
• 空间复杂度：O(N)。借助了大小为N的栈来辅助完成

---

第二题（leetcode32_最长有效括号）

思路

对于每个’(‘，我们将它的下标进栈。对于每个’)’，我们弹出栈顶的元素并将当前元素的下标于当前栈顶下标作差，得出当前有效括号的长度。

代码

package leetcode;

import java.util.Stack;

/**
 * @author god-jiang
 * @date 2020/1/30  11:59
 */
public class LongestValidParentheses {
    public int longestValidParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int max = 0;
        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 {
                    max = Math.max(max, i - stack.peek());
                }
            }
        }
        return max;
    }
}

复杂度分析

• 时间复杂度：O(N)。因为遍历一次就能得出最长的有效括号
• 空间复杂度：O(N)。因为借助了大小为N的辅助栈处理