0001 #include "stack/stack.h" //借助栈结构,计算直方图H[]中的最大矩形(并列时取最靠左者) 0002 0003 __int64 mr_STACK( int H[], int n, int& mr_r, int& mr_s, int& mr_t ) { //H[]皆非负 0004 Stack<int> SR; //次栈顶、栈顶总是s[r]-1与r,当前的t = t[r] 0005 __int64 maxRect = 0; 0006 for ( int t = 0; t <= n; t++ ) { //逐个尝试以t为右边界的 0007 while ( !SR.empty() && ( t == n || H[SR.top()] > H[t] ) ) { //每一个极大矩形 0008 int r = SR.pop(); int 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)