java - 如何在最长子数组的长度平衡问题中找到开始位置和结束位置

Question

给定一些花括号，包括左花括号和右花括号。找到平衡的最长子数组的长度。另外，找到 longes 子数组的位置

那是平衡的开始和结束。如果多个子数组具有相同的长度，请考虑第一个。

输入

5

{}{}{

输出

4

1 4

解释

{}{} 是平衡的，长度为 4。它从位置 1 开始，到位置 4 结束（基于 1 的索引）

我有长度，但我无法获得第一个位置和最后一个位置。有人可以告诉如何调整函数以获得第一个位置和最后一个位置吗？

int findMaxLen(string str) 
{ 
    int n = str.length(); 
    stack<int> stk; 
    stk.push(-1); 

    int result = 0; 

    for (int i=0; i<n; i++) 
    { 
        if (str[i] == '{') 
          stk.push(i); 

        else 
        { 
            stk.pop(); 

            if (!stk.empty()) 
                result = max(result, i - stk.top()); 
            else stk.push(i); 
        } 
    } 

    return result; 
} 

标签： javaalgorithmdata-structuresdivide-and-conquer

Answer 1

有人可以告诉如何调整函数以获得第一个位置和最后一个位置吗？

您只跟踪迄今为止最大平衡子串的长度。您还需要跟踪它的开始或结束索引，所以而不是

                result = max(result, i - stk.top());

使用if具有相应条件的块：

                  if (result < i - stk.top()) {
                      // ...
                  }

. 在该块的主体中​​，更新两者result以及相应的结束或开始索引。完成后，长度和一个索引的组合会为您提供另一个索引。细节留作练习。