题解

题目难度：简单

知识点：字符串、数组、栈

分析：

因为题目本身是针对合法字符串求深度，省去了判断字符串是否合法的步骤，所以该题较简单，下面给出2种解法

方法1： 利用数组，统计到当前位置Xi时连续左括号的长度

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();

        // 1. 利用数组解决
        int res = arraySolve(s);
        System.out.println(res);
    }

    private static int arraySolve(String strs) {
        if(strs==null || strs.length()==1){
            return 0;
        }

        int count = 0;
        int[] nums = new int[strs.length()];
        for(int i = 0; i<strs.length();i++){
            if(strs.charAt(i)=='('){
                nums[i]=++count;
            }else{  //  )说明有匹配的出现了
                nums[i]=--count;  
            }
        }
        Arrays.sort(nums);
        return nums[nums.length-1];

    }

}

方法2： 利用栈，左括号入栈，右括号出栈，并在出栈前统计栈的大小，也就是求出栈的最大深度即可。

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();

        // 2. 利用单调栈解决
        int res = stackSolve(s);
        System.out.println(res);
    }



    private static int stackSolve(String s) {
        if(s==null || s.length()==1){  //其实在本题中不存在这种情况
            return 0;
        }

        Stack<Character> stack = new Stack<>();
        int count = Integer.MIN_VALUE;

        // '('入栈，  ')'弹栈并在弹栈前更新结果
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '(' ){
                stack.push('(');
            }else{
                count = Math.max(count, stack.size());
                stack.pop();
            }
        }
        return count;
    }

}