本題有非常直接的解法,根據(jù)輸入先將括號字符串還原,再對還原后的括號字符串進行計算,但效率不高,需要n²+n的時間復雜度,其實可以用線性掃描在O(n)的時間內(nèi)解決,具體思路如下:
在掃描的時候,利用一個棧保存已有的左括號信息(包括剩下幾個未匹配的左括號與已經(jīng)匹配左括號的個數(shù)),在掃描到輸入j的時候,有以下三種情況(設i為j前一個輸入):
1. i == j - 1;這種情況非常簡單,表明新輸入的右括號與自身所帶的左括號匹配,直接輸出1,更新棧頂元素信息.
2. i < j - 1; 這種輸入表明j位置上的右括號自帶了比自身所需更多的左括號,將剩余的左括號相關信息入棧保存.
3. i == j;表明位置j并沒有任何自身的左括號,需要向棧中借,并更新棧相關信息.

Code
  1#include <vector>
  2#include <iostream>
  3using namespace std;
  4
  5class Info
  6{
  7public:
  8    int left;
  9    int have;
 10};
 11
 12template <class T>
 13class Stack
 14{
 15private:
 16    vector<T> v;
 17public:
 18    void push(const T & t)
 19    {
 20        v.push_back(t);
 21    }
 22
 23    T & pop()
 24    {
 25        T & temp = v[v.size() - 1];
 26        v.pop_back();
 27        return temp;
 28    }
 29
 30    T & top()
 31    {
 32        return v[v.size() - 1];
 33    }
 34
 35    int size() const
 36    {
 37        return v.size();
 38    }
 39};    
 40
 41int _tmain(int argc, _TCHAR* argv[])
 42{
 43    int num;
 44    cin >> num;
 45    Stack<Info> s;
 46
 47    while(num--)
 48    {
 49        int n;
 50        cin >> n;
 51        int * parenttheses = new int[n];
 52        
 53        for(int i = 0; i < n; ++i)
 54        {
 55            cin >> parenttheses[i];
 56        }
 57
 58        Info original;
 59        s.push(original);
 60
 61        for(int i = 0; i < n; ++i)
 62        {
 63            if(i == 0)
 64            {
 65                s.top().left = parenttheses[i] - 1;
 66                s.top().have = 1;
 67                cout << "1 ";
 68            }
 69            else
 70            {
 71                // except the nearby one, we still have more left parenttheses, store them into stack
 72                if(parenttheses[i] - parenttheses[i - 1] > 1)
 73                {
 74                    Info new_info;
 75                    new_info.have = 1;
 76                    new_info.left = parenttheses[i] - parenttheses[i - 1] - 1;
 77                    s.push(new_info);
 78                    cout << "1 ";
 79                }
 80                // the right parenttheses just pair with the nearby left one
 81                else if(parenttheses[i] - parenttheses[i - 1] == 1)
 82                {
 83                    if(i != n - 1)
 84                    {
 85                        cout << "1 ";
 86                        if(s.size() > 0)
 87                            ++s.top().have;
 88                    }
 89                    else
 90                    {
 91                        cout << "1";
 92                    }
 93                }
 94                // no nearby left one exists, need to borrow from stack
 95                else
 96                {
 97                    --s.top().left;
 98                    ++s.top().have;
 99
100                    // if it's not the last one
101                    if(i != n - 1)
102                    {
103                        cout << s.top().have << " ";
104                    }
105                    else
106                    {
107                        cout << s.top().have;
108                    }
109
110                    if(s.top().left == 0)
111                    {
112                        Info last = s.pop();
113                        if(s.size() != 0)
114                        {
115                            s.top().have += last.have;
116                        }
117                    }
118                }
119            }
120            if(i == n - 1)
121                cout << endl;
122        }
123
124        delete parenttheses;
125    }
126    return 0;
127}
128
129