#C. 时间复杂度

传统题1000ms256MiB

复杂度判断

今天面条老师给大家讲解了算法复杂度（也可称为时间复杂度）的计算，并布置了作业题。面条老师在一个程序中写了很多个 for 循环，每一个 for 循环都是形如 for(int i = 1; i <= n; i++) ，且中间没有 continue，break 等影响循环执行的语句，即每一个 for 都会运行 n 轮（注意，并不是每一个循环里面定义的变量都叫 i，但是这个循环变量一定是从 1 到 n，执行 n 次）。现在面条老师想知道，他写的这个程序的算法复杂度是 n 的几次方。

在本题中，你可以将“算法复杂度”理解为“for循环最多嵌套的层数”。

输入描述

输入一个长度为 2n 的字符串，字符串的内容只可能是 0 或者 1，且 0 和 1 的数量相等。0 代表一个 for 循环的开始，1 代表一个 for 循环的结束。保证字符串合法。

输出描述

输出一行一个整数代表这个程序的算法复杂度是 n 的多少次方。

输入数据 1

001101

Copy

输出数据 1

2

Copy

输入数据 2

010101

Copy

输出数据 2

1

Copy

解释：

样例 1 中，最多有两层循环嵌套，即 0011，所以算法复杂度是 n²，所以输出 2。

将样例 1 转化为代码即为：

for (int i = 1; i <= n; i++)
{
	for(int j = 1; j <= n; j++)
	{
	
	}
}
for (int i = 1; i <= n; i++)
{

}

Copy

样例 2 中，最多有一层循环嵌套，所以输出 1。

应该和括号匹配有点像！ 用栈吗？？？