栈-LeetCode32-最长有效括号

题目

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

思路

明显地，使用栈。将成对的括号转化为数字。遍历输入的字符串，分为以下情况：

1. 如果是 '(' :  push入栈

2. 如果是 ')'

    2.1 如果左一（下一）为 ')' : push入栈

    2.2 如果左一超范围（栈空）: push入栈

    2.3 如果左一为 '(' : 与左一'(' 组合成 "()",替换为数字2。将数字2与左侧所有数字求和并替代之。

    2.4 如果左一为数字

          2.4.1 如果左二为 ')' : push入栈

          2.4.2 如果左二超范围 : push入栈

          2.4.3 如果左二为'(': 与左二'(' 组合成"(数字a)",替换为数字(a+2)。将数字(a+2)与左侧所有数字求和并替代之。

栈中最大数字即为所求。

代码

class Solution {
    public int longestValidParentheses(String s) {
        int res=0;
        Stack<String> stack=new Stack<String>();
        
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                stack.push(s.charAt(i)+"");
            }else{
                if(stack.empty() || stack.peek().equals(")") ){
                    stack.push(s.charAt(i)+"");
                }else if(stack.peek().equals("(") ){
                    stack.pop();
                    stack.push("2");
                    int count=0;
                    while(true){
                        if(stack.empty() || stack.peek().equals("(") || stack.peek().equals(")") ){
                            stack.push(count+"");
                            break;
                        }else{
                            count+=Integer.parseInt(stack.pop());
                        }
                    }
                }else{
                    // 左1为数字
                    // 拿到左2
                    String zuo1=stack.pop();
                    if(stack.empty()){
                        stack.push(zuo1);
                        stack.push(s.charAt(i)+"");
                    }else{
                        String zuo2=stack.peek();
                        stack.push(zuo1);
                        if(zuo2.equals(")")){
                            stack.push(s.charAt(i)+"");
                        }else if(zuo2.equals("(")){
                            int zuo1num=Integer.parseInt(stack.pop());
                            stack.pop();
                            stack.push((zuo1num+2)+"");
                            int count=0;
                            while(true){
                                if(stack.empty() || stack.peek().equals("(") || stack.peek().equals(")") ){
                                    stack.push(count+"");
                                    break;
                                } else  {
                                    count+=Integer.parseInt(stack.pop());
                                }
                            }
                        }
                    }
                   
                }
            }
        }
        
        while(true){
            if(stack.empty()){
                break;
            }
            if(stack.peek().equals("(") || stack.peek().equals(")")){
                stack.pop();
            }else{
                if(res<Integer.parseInt(stack.peek())){
                    res=Integer.parseInt(stack.pop());
                }else{
                    stack.pop();
                }
            }
        }
        return res;
    }
}

总结

1.将成对的括号转化为数字

2. Stack

Stack<String> stack=new Stack<String>();

if( stack.empty() ) { }

String s=stack.pop()

stack.push(s)

stack.peek()      // 查看堆栈顶部的对象，但不从堆栈中移除