0001 #include "stack/stack.h" //借助栈结构，计算直方图H[]中的最大矩形（并列时取最靠左者）
0002 
0003 __int64 mr_STACK( int H[], Rank n, Rank& mr_r, Rank& mr_s, Rank& mr_t ) { //H[]皆非负
0004    Stack<Rank> SR; //次栈顶、栈顶总是s[r]-1与r，当前的t = t[r]
0005    __int64 maxRect = 0;
0006    for (Rank t = 0; t <= n; t++ ) { //逐个尝试以t为右边界的
0007       while ( !SR.empty() && ( t == n || H[SR.top()] > H[t] ) ) { //每一个极大矩形
0008          Rank r = SR.pop(), s = SR.empty() ? 0 : SR.top() + 1;
0009          __int64 mR = H[r] * ( t - s );
0010          if ( maxRect < mR )
0011             { maxRect = mR; mr_r = r; mr_s = s; mr_t = t; }
0012       }
0013       if ( t < n ) SR.push( t ); //栈中只记录所有的H[s] = min{ H[k] | s <= k <= t }
0014    } //assert: SR is empty at exit
0015    return maxRect;
0016 } //每项进栈、出栈不过常数次，累计成本O(n)