1

首先，将一串“平衡”括号定义为一个字符串，这样对于每个“（”，在该“（”之后的某处都有一个唯一的匹配的“）”。

例如，以下字符串都是“平衡的”：

()

()()

(())()

虽然这些不是：

)(

())(

给定一个括号字符串（长度 <= 1,000,000）和一个范围查询列表，找到每个 <= 100,000 个查询的每个范围内平衡括号的最大长度（对范围使用 0 索引）

前任：

()))()(())

范围：[0,3] -> 最长 = 2：“()”

范围：[0, 4] -> 最长 = 2：“()”

范围：[5, 9] -> 最长 = 4：“(())”

我的想法如下：

首先，只要确定一个字符串是否“平衡”就可以通过维护一个堆栈来完成。如果遇到'('，则压入堆栈，遇到')'，则从堆栈中弹出。如果最后有任何 '(' 仍然存在，则字符串不是“平衡的”。

但是，对所有范围重复此操作是 O(N*M) 复杂度，这对于输入的大小来说太长了。

现在，在注意到范围查询时，会想到前缀和和二叉索引树/段树。如果您可以将整个前缀和范围预先计算到一个数组中，那么您可以通过取差来找到更小的前缀和，这将具有良好的 big-o 复杂性。

我的想法是给'（'分配一个+1值，给'）'分配一个-1值，这样每次你遇到'（'你加一个到累积和当你遇到'） '你减少了。因此，对于一个有效的“平衡”字符串，))()你会得到：-1 -2 -1 -2.

但是，我的问题是您如何使用它来确定它是否“平衡”？此外，因为您需要在给定间隔内找到最大的“平衡”字符串，所以如何使用检查给定子字符串是否“平衡”的能力来找到该给定间隔内的最大字符串。

4

1 回答 1

1

介绍

对于 position 的每个起始括号x，您希望在 position 找到匹配的右括号y，这样从xto的子串y, S[x, y], 是平衡的最大子串。我们对从右括号开始的子字符串不感兴趣，因为从那里开始的字符串最多与从第一个随后的左括号开始的字符串一样好。

最重要的观察如下：对于从某个位置开始的每个左括号x'for x < x' < y，匹配的右括号在y'where x' < y' < y。这是因为每个前缀S[x, y]至少包含与右括号一样多的左括号，因此最多S[x', y]包含与右括号一样多的左括号。

我们可以利用这些知识来构建一棵树，其中每个节点代表一个最大平衡子串，因此它有一个起始位置和一个结束位置。这个节点的子节点代表这个顶级子串的平衡子串。由于可能存在与左括号不匹配的右括号，因此没有单个根，因此我们实际上有一个森林1。

一张图说一千多个字。考虑这个例子：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
) ) ( ( ) ( ( ) ) )  )  (  (  )  )

这将给出以下树：

   (2, 9)       (11, 14)
   /     \          |
(3, 4) (5, 8)   (12, 13)
          |
       (6, 7)

构建树

建造树真的很容易。从一个空堆栈开始。每当您在位置遇到左括号时x：

  • 创建一个节点(x, ..)
  • 将该节点添加为当前位于堆栈顶部的节点的子节点（如果存在，否则这是根节点）
  • 将新节点压入堆栈

每当您在 position 遇到右括号时y：

  • 弹出(x, ..)堆栈顶部的节点（如果没有这样的节点，这是一个不匹配的右括号：忽略）
  • 设置收盘指数：(x, y)

您扫描字符串一次并在每个步骤中执行恒定数量的操作，因此构建结构是在线性时间内完成的。

查询树

现在您需要运行查询。给定一个查询(p, q)，您需要找到y - x + 1完全包含在 中的最大节点（其中 size 为 ）(p, q)。只需进行两次二进制搜索即可找到树中的开始和结束位置。（如果 position 处的字符p是右括号，则查找最小的x > p。类似地，如果 positionq处的字符是左括号，则查找最大的y < p。）沿路径 找到 和 的最大x间隔y。

如果您的树非常平衡，则每个查询都需要O(lg n)时间。最坏的情况是，字符串以所有左括号开始并以所有右括号结束。然后查询可能会占用线性时间。

1我们可以通过在字符串前面添加与不匹配的右括号一样多的左括号来解决此问题。

于 2014-10-28T07:50:49.770 回答