如何利用Java实现最大括号深度 |21xrx.com

如何利用Java实现最大括号深度

2023-06-13 03:46:03 深夜i -- --

Java 括号匹配栈数据结构字符串

在计算机科学领域，括号匹配问题一直是一个热门话题。其中，最大括号深度问题是其中之一。最大括号深度指的是一段字符串中，最深层嵌套的括号的层数。例如，字符串 "((()))" 的最大括号深度为 3，而字符串 "(()()())" 的最大括号深度为 1。

Java语言作为一门广泛应用于计算机科学领域的语言，在解决最大括号深度问题时也有着非常好的应用场景。根据问题的定义，我们可以使用栈这一数据结构来辅助解决。

具体来说，我们可以对于每个左括号 '('，将其下标入栈；而对于每个右括号 ')'，则将栈顶的左括号出栈，并计算当前最大深度。代码实现如下：


public static int getMaxDepth(String s) {
  Stack
  stack = new Stack 
  
   ();
  
 
  int maxDepth = 0;
  for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    if (c == '(') {
      stack.push(i);
    } else if (c == ')') {
      if (stack.isEmpty()) 说明存在未匹配的右括号
       else {
        stack.pop();
        int currentDepth = stack.isEmpty() ? i + 1 : i - stack.peek();
        maxDepth = Math.max(maxDepth, currentDepth);
      }
    }
  }
  if (!stack.isEmpty()) 说明存在未匹配的左括号
  
  return maxDepth;
}

该方法首先创建一个存放下标的栈和一个变量 maxDepth，初始值为 0。遍历字符串，如果当前字符为左括号，则将其下标入栈。如果当前字符为右括号，则弹出栈顶的左括号，然后计算当前深度（即右括号下标减去左括号下标，如果栈为空则当前深度为 i + 1）。每次计算后更新最大深度值。在遍历结束后，如果栈非空，则存在未匹配的左括号，返回 -1。如果栈已经为空，则返回最大深度值。

上一篇: idea打包java可执行jar包

下一篇: 我和JavaScript的不解之缘

评论区

()

相似文章