0001 #include "stack/stack.h" //借助栈结构,计算直方图H[]中的最大矩形(并列时取最靠左者) 0002 0003 __int64 mr_STACKS( int H[], int n, int& mr_r, int& mr_s, int& mr_t ) { //除末项-1哨兵,H[]皆非负 0004 int* s = new int[n]; Stack<int> S; //自右可见项的秩 0005 for( int r = 0; r < n; r++ ) { //依次计算出 0006 while ( !S.empty() && H[S.top()] >= H[r] ) S.pop(); //每一个s(r) 0007 s[r] = S.empty() ? 0 : 1 + S.top(); 0008 S.push(r); 0009 } 0010 while( !S.empty() ) S.pop(); 0011 0012 int* t = new int[n]; Stack<int> T; //自左可见项的秩 0013 for( int r = n-1; -1 < r; r-- ) { //依次计算出 0014 while ( !T.empty() && H[r] <= H[T.top()] ) T.pop(); //每一个t(r) 0015 t[r] = T.empty() ? n : T.top(); 0016 T.push(r); 0017 } 0018 while( !T.empty() ) T.pop(); 0019 0020 __int64 maxRect = 0; 0021 for( int r = 0; r < n; r++ ) { 0022 __int64 mR = H[r] * (t[r] - s[r]); 0023 if ( maxRect < mR ) 0024 { maxRect = mR; mr_r = r; mr_s = s[r]; mr_t = t[r]; } 0025 } 0026 delete [] s; delete [] t; 0027 return maxRect; 0028 } //每项进栈、出栈不过常数次,累计成本O(n)