【算法题】最大括号深度

845次阅读
一条评论

共计 1209 个字符,预计需要花费 4 分钟才能阅读完成。

import java.util.Scanner;
import java.util.Stack;
/**
 * 标题:最大括号深度 | 时间限制:1秒 | 内存限制:262144K | 语言限制:不限
 * 现有一字符串仅由 '(',')','{','}','[',']'六种括号组成。
 * 若字符串满足以下条件之一,则为无效字符串:
 * ①任一类型的左右括号数量不相等;
 * ②存在未按正确顺序(先左后右)闭合的括号。
 * 输出括号的最大嵌套深度,若字符串无效则输出0。
 * 0≤字符串长度≤100000
 * 输入描述:
 * 一个只包括 '(',')','{','}','[',']'的字符串
 * 输出描述:
 * 一个整数,最大的括号深度
 * 示例1
 * 输入
 * []
 * 输出
 * 1
 * 说明
 * 有效字符串,最大嵌套深度为1
 * 示例2
 * 输入
 * ([]{()})
 * 输出
 * 3
 * 说明
 * 有效字符串,最大嵌套深度为3
 * 示例3
 * 输入
 * (]
 * 输出
 * 0
 * 说明
 * 无效字符串,有两种类型的左右括号数量不相等
 * 示例4
 * 输入
 * ([)]
 * 输出
 * 0
 * 说明
 * 无效字符串,存在未按正确顺序闭合的括号
 * 示例5
 * 输入
 * )(
 * 输出
 * 0
 * 说明
 * 无效字符串,存在未按正确顺序闭合的括号
 */
public class M_N_T_38 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.nextLine();
        char[] chars = line.toCharArray();

        deal(chars);
    }

    private static void deal(char[] chars) {
        Stack<Character> stack = new Stack<>();
        int deep_max = 0;
        for (char aChar : chars) {
            if (aChar == '(' || aChar == '[' || aChar == '{') {
                stack.push(aChar);
                deep_max = Math.max(stack.size(), deep_max);
                continue;
            }

            if (stack.size() == 0) {
                System.out.println(0);
                return;
            }

            Character character = stack.pop();

            if (aChar == ')') {
                if (character == '(') {
                    continue;
                }
                System.out.println(0);
                return;
            }

            if (aChar == ']') {
                if (character == '[') {
                    continue;
                }
                System.out.println(0);
                return;
            }

            if (aChar == '}') {
                if (character == '{') {
                    continue;
                }
                System.out.println(0);
                return;
            }
        }

        System.out.println(stack.size() == 0 ? deep_max : 0);
    }
}
正文完
 0
裴先生
版权声明:本站原创文章,由 裴先生 2022-05-11发表,共计1209字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(一条评论)
ENUYGsbKPlLQqHc 评论达人 LV.1
2024-03-15 22:36:11 回复

算法题最大括号深度

 Windows  Chrome  伊朗
本站勉强运行: