0001 using Rank = unsigned int; 0002 0003 // 按定义蛮力地计算直方图H[]中的最大矩形(多个并列时取最靠左侧者) 0004 __int64 mr_BRUTE( int H[], Rank n, Rank& mr_r, Rank& mr_s, Rank& mr_t ) { //蛮力:O(n^2) 0005 __int64 maxRect = 0; 0006 for ( Rank r = 0, s = 0, t = 0; r < n; r++, s = t = r ) { 0007 do s--; while ( (-1 != s) && (H[s] >= H[r]) ); s++; 0008 do t++; while ( (t < n) && (H[r] <= H[t]) ); 0009 __int64 rect = (__int64) H[r] * ( t - s ); 0010 if ( maxRect < rect ) 0011 { maxRect = rect; mr_r = r; mr_s = s; mr_t = t; } 0012 } 0013 return maxRect; 0014 } //每个极大矩形耗时O(n),累计O(n^2)