[数据结构与算法]leetcode32.最长有效括号——学习笔记

题目：力扣https://leetcode-cn.com/problems/longest-valid-parentheses/

import java.util.Stack;
class Solution {
    public int longestValidParentheses(String s) {
        int len = s.length();
        int num = 0;
        int max_num = 0;
        char[] Str = s.toCharArray();
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(-1);
        for(int i=0;i<len;i++){
            if(Str[i] == '('){
                stack.push(i);
            }else{
                    stack.pop();
                    if(stack.isEmpty()){
                        stack.push(i);
                        num = 0;
                        continue;
                    }
                    num = i-stack.peek();
                    max_num = Math.max(max_num,num);
            }
        }
        return max_num;
    }
}

?

思路：我是利用栈解决这道题的。一开始，没有留意到题目的”格式正确且连续“这七个字，然后一顿敲，敲出来的代码是求有效括号的。其实这道题的难点不是”格式正确“而是”连续“，这需要判断到底哪个括号是无效的括号。首先需要在栈底垫一个”-1“，栈底垫着的元素相当于分界线。遇到”（“就压入栈中，遇到”）“就弹出一个栈中元素，若栈为空则将该元素压入栈中充当分界线。在弹出栈中元素的同时，用num记录。最后返回max_num。

1.准备阶段。len用于记录给定字符串的长度；num用于记录给定字符串中单个连续有效括号的片段的长度；max_num用于记录当前最长有效括号长度。通过toCharArray()的方法将字符串转换成字符数组。初始化一个栈stack，将-1元素压入栈底。（将-1元素压入栈底意味着-1是一条无形的分界线，计算有效括号长度只能从0的位置开始计算。）

int len = s.length();
int num = 0;
int max_num = 0;
char[] Str = s.toCharArray();
Stack<Integer> stack = new Stack<Integer>();
stack.push(-1);

2.从头开始遍历字符数组，直至遍历完成。循环内的判断与操作见后续。

for(int i=0;i<len;i++){
    //......
}

3.遇上“（”想都不需要想直接压入栈中；遇上“）”则将栈顶元素弹出，若栈不为空则正常按i-stack.peek()计算num的值，如果num的值大于max_num的值，则将num的值赋予给max_num；若将栈顶元素弹出后栈为空，则表示当前位置的括号是无法匹配的，为分界线，重置num的值跳出当前循环继续向后遍历。

if(Str[i] == '('){
    stack.push(i);
}else{
    stack.pop();
    if(stack.isEmpty()){
        stack.push(i);
        num = 0;
        continue;
    }
    num = i-stack.peek();
    max_num = Math.max(max_num,num);
}

4.最后返回最长有效括号的长度。

return max_num;