贪心算法：括号的平衡配对问题

本课继续讲解贪心算法相关的习题：括号的平衡配对问题。

在编写计算机程序的时候，新手常犯的一个错误就是括号的配对问题，比如，在C/C++语言中，{ 需要和 } 相匹配。今天我们就来看一个与括号匹配相关的问题。

假设有一个字符串，它仅由两种字符组成：左括号 [ 和 右括号 ]，并且包含N个左括号 [ 和 N个右括号 ]，一共2N个字符。但是我们需要让字符串中的 [ 和 ] 排列次序达成某种平衡，也就是 [ 和 ] 的排列必须符合下面的规则：

空字符串是括号平衡的；

字符串A是括号平衡的，那么左右分别添加 [ 和 ] 后得到的新字符串 [ A ] 也是括号平衡的；

字符串A和字符串B是括号平衡的，那么合并字符串 AB 是括号平衡的，合并字符串 BA 也是括号平衡的。

例如:

[] 、[[]]、[][][]、[[][]] 等等都是括号平衡字符串。

][、[]][、][][[] 等等都不是括号平衡的。

为了使非括号平衡的字符串达到括号平衡，可以通过交换相邻的 [ 和 ] 的位置，达到括号平衡。例如：

1）交换 ][ 中第一个字符和第二个字符位置，得到的新字符串 [] 是括号平衡的

2）交换 []][ 中第三个字符和第四个字符位置，得到的新字符串 [][]是括号平衡的

3）交换 ][][[]中第一个字符和第二个字符位置，再交换第三个字符和第四个字符位置，得到的新字符串 [][][]是括号平衡的

问题来了：

给出一串由N个左括号 [ 和 N个右括号 ]组成的字符串，请计算最少需要进行多少次相邻符号的交换才能使它达到括号平衡？

【例题1】

输入 : []][][

输出 : 需要2次交换

第一次交换: 位置3和位置4，得到[][]][

第二次交换: 位置5和位置6，得到[][][]

【例题2】

输入: [[][]]

输出 : 需要0次交换

因为该输入字符串本来已经是括号平衡了.

在继续讲解算法之前，请你自己先思索一下如何解决上述问题。

思路分析

如果我们仔细观察一下括号平衡的字符串，会发现下列事实：

如果前X个字符可以形成一个括号平衡字符串A，那么A对它后面的字符串是否平衡没有影响。也就是整个字符串是否平衡将由A以后的字符串决定。例如：[][[]]][中红色部分是平衡字符串，它不影响整个字符串的平衡性，而由于][不平衡，导致了整个字符串的不平衡。

平衡字符串一定是以'['开始的。

因此，我们可以使用贪心算法来解决这个问题，并且采取如下的贪心策略：

如果前X个字符形成一个平衡字符串，我们可以忽略这些字符并继续检查后面的字符。

平衡字符串一定是以'['开始的，所以如果在需要'['之前先遇到']'，那么必须开始交换字符以获得平衡字符串。

算法描述

具体的算法描述如下：

变量sum保存需要交换的次数，初始化sum = 0

设置当前字符索引 i = 0, 指向第一个字符

计数器counter 设为0

通过索引 i 和依次递增 i 的 值，从左到右遍历字符串，统计左括号 [ 的数量: 遇到左括号 [，计数器counter 就加上 1，当遇到右括号 ] 时计数器就减去1

如果计数器counter 变为负数，那么就表示遇到 ] 了，就必须开始把它与它后面的第一个 [ 交换来平衡字符串，执行下列操作：

索引 i 代表我们当前所处的位置，现在我们继续前进到下一个左括号 [ 所在的位置，假设是索引 j 的位置 。把位于j 的 左括号 [ 通过依次相邻交换到位置i, 将位置i和位置j之间的所有其他字符移到右侧，共需要交换 j-i 次，所以我们必须把 j-i 的值累加到sum中。

转步骤3）

采用上述算法计算【例题1】的过程可以用下面的动图来表示。

算法的优化

上述算法的时间复杂性为 O(N^2)，因为交换字符的时候，需要搜索下一个 [，这个操作需要O(N)的复杂性。

我们可以先扫描字符串并将左括号 [ 的位置存储在向量pos中，并用p表示当前处理到的左括号在向量pos中的位置。

与原来的算法类似，计数器counter计算遇到的左括号的数量：遇到左括号 [ 增加计数，注意此时将p加1，我们遇到右括号 ] 时，减少计数。

如果计数器小于0，意味着我们必须开始交换。注意此时元素pos [p] 告诉我们下一个左括号 [ 的索引位置。计算 pos [p] - i，并将差加入到sum中，其中 i 是当前位置。 我们可以交换当前索引i指向的元素和pos [p]指向的元素，并将counter重置为0。

由于我们已经将原来算法中的O（N）步骤转换为O（1）步骤了，因此总的时间复杂度降低到了O(N)。

代码实现

我们还是使用C++的STL来简化编程。具体的代码实现如下：

//字符串的括号平衡问题

#include

#include

#include

using namespace std;

// 计算需要交换的次数

long swapCount(string s)

{

// 向量pos 记录 [ 的位置

vector pos;

for (int i = 0; i

if (s[i] == '[')

pos.push_back(i);

int counter = 0; // 存放遇到的[的个数

int p = 0; // 指向下个 [在向量pos中的位置

long sum = 0; // 记录需要交换的总次数

for (int i = 0; i

{

// 遇到[将计算器加1，并让p加1，使它指向向量pos记录的下一个[的位置

if (s[i] == '[')

{

++counter;

++p;

}

else if (s[i] == ']')

--counter;

// 遇到不平衡的括号

if (counter

{

//把需要交换的次数加入到总的次数sum中

sum += pos[p] - i;

swap(s[i], s[pos[p]]);

++p;

// 重置计数器为1

counter = 1;

}

}

return sum;

}

// 主程序

int main()

{

string s = "[]][][";

cout

s = "[[][]]";

cout

return 0;

}