0001 uint64_t mr2Pass(uint64_t H[], Rank n) { //两趟扫描版
0002    Stack<Rank> S; Rank* s = new Rank[n]; //单调栈S，左限数组O(n)空间
0003    for (Rank r = 0; r < n; r++) { //依次检视每根H[r]
0004       while (!S.empty() && (H[S.top()] >= H[r])) S.pop(); //保持单调
0005       s[r] = S.empty() ? 0 : S.top() + 1; //确定左限s(r)
0006       S.push(r); //保持单调
0007    }
0008    while (!S.empty()) S.pop(); //S使命完成，可以清空
0009 
0010    Stack<Rank> T; Rank* t = new Rank[n]; //单调栈T，右限数组O(n)空间
0011    for (Rank r = n-1; -1 != r; r--) { //依次检视每根H[r]
0012       while (!T.empty() && H[r] <= H[T.top()]) T.pop(); //保持单调
0013       t[r] = T.empty() ? n : T.top(); //确定右限t(r)
0014       T.push(r); //保持单调
0015    }
0016    while (!T.empty()) T.pop(); //T使命完成，可以清空
0017 
0018    uint64_t maxRect = 0;
0019    for (Rank r = 0; r < n; r++) //算出每个极大矩形的面积，并择优更新
0020       maxRect = max(maxRect, H[r] * (t[r] - s[r]));
0021    delete[] s; delete[] t;
0022    return maxRect; //最大的极大矩形，即是最大矩形
0023 } //每项进栈、出栈不过常数次，累计成本O(n)