我认为是一道很值得做的栈的题目
告诉你两种标记括号的方式
第一种：第i个 ) 左边的 ( 数量
第二种:第i个)与跟它配对的(的中间，有多少个已经配对的括号对，记为x,那么第i个)标记为x+1
题目告诉了第一种标记方法，求第二种
很容易通过第一种标记方法求出 括号串
重点是如何求第二种，我是这样想的
用栈维护左括号与跟它配对的右括号中已经配对的个数
遍历括号串，遇到(的时候，压入0到栈中
遇到)的时候，将栈顶取出，这个是与)配对的，那么答案就是记为t = top() + 1，，并弹出栈顶
再取出一个栈顶，并弹出，记为f，这个(是在上一个已经配对的括号对的外面的，换句话说，上次的括号配对是在这个括号内部完成的，所以在上个括号内部完成的配对数，要更新到这个括号里来，所以再把f + t压入栈中
于是题目就做完了
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<cctype>
#include<stack>
#include<vector>
#include<functional>
#include<algorithm>using namespace std;
typedef long long LL;
typedef pair<int, int> PII;const int MX = 100 + 5;
const int INF = 0x3f3f3f3f;char S[MX];
int tot;int main() {int T, n, t;scanf("%d", &T);while(T--) {tot = 0;scanf("%d", &n);int sum = 0;for(int i = 1; i <= n; i++) {scanf("%d", &t);for(int i = sum; i < t; i++) {S[tot++] = '(';}sum = t;S[tot++] = ')';}S[tot] = 0;stack<int>work;for(int i = 0; i < tot; i++) {if(S[i] == '(') {work.push(0);} else {int t = work.top() + 1;work.pop();printf("%d%c", t, i == tot - 1 ? '\n' : ' ');if(!work.empty()) {int f = work.top();work.pop();work.push(f + t);}}}}return 0;
}