0001 #include <cstdlib> 0002 #include <ctime> 0003 #include <cstdio> 0004 0005 __int64 mr_STACK ( int H[], int n, int& r, int& s, int& t ); //借助一个栈:O(n) 0006 __int64 mr_STACKS( int H[], int n, int& r, int& s, int& t ); //借助两个栈:O(n) 0007 __int64 mr_BRUTE ( int H[], int n, int& r, int& s, int& t ); //蛮力:O(n^2) 0008 0009 /****************************************************************************************** 0010 * 直方图中的最大矩形 0011 ******************************************************************************************/ 0012 int main ( int argc, char* argv[] ) { 0013 int* H; int n; //宽度为n的直方图 0014 if ( 1 < argc ) { //命令行指定,比如:77 4 120 16 96 59 0 15 123 8 79 73 57 96 84 101 26 12 88 81 111 18 87 117 46 90 94 70 125 0015 H = new int[ n = argc -1 ]; 0016 for ( int i = 0; i < n; i++ ) 0017 H[i] = atoi( argv[i+1] ); 0018 } else { //随机生成 0019 srand ( ( unsigned int ) time ( NULL ) ); 0020 H = new int[ 1 + ( n = rand() % 128 ) ]; 0021 for ( int i = 0; i < n; i++ ) 0022 H[i] = rand() % 128; 0023 } 0024 0025 int r, s, t; //最大矩形:H[r] x [s, t) 0026 __int64 mrBrute = mr_BRUTE( H, n, r = -1, s = -1, t = -1 ); 0027 printf( "MaxRect Brute-Force : %I64d = %d x [%d,%d)\n", mrBrute, H[r], s, t ); 0028 __int64 mrStacks = mr_STACKS( H, n, r = -1, s = -1, t = -1 ); 0029 printf( "MaxRect using STACKS : %I64d = %d x [%d,%d)\n", mrStacks, H[r], s, t ); 0030 __int64 mrStack = mr_STACK ( H, n, r = -1, s = -1, t = -1 ); 0031 printf( "MaxRect using STACK : %I64d = %d x [%d,%d)\n", mrStack, H[r], s, t ); 0032 0033 for ( int i = 0; i < s; i++ ) { 0034 printf("%3d:%4d : ", i, H[i]); 0035 for ( int j = 0; j < H[i]; j++ ) printf("."); printf("\n"); 0036 } 0037 for ( int i = s; i < r; i++ ) { 0038 printf("%3d:%4d : ", i, H[i]); 0039 for ( int j = 0; j < H[i]; j++ ) printf( (j < H[r]) ? "#" : "." ); printf("\n"); 0040 } 0041 { 0042 printf("%3d:%4d : ", r, H[r]); 0043 for ( int j = 0; j < H[r]; j++ ) printf("O"); printf("\n"); 0044 } 0045 for ( int i = r+1; i < t; i++ ) { 0046 printf("%3d:%4d : ", i, H[i]); 0047 for ( int j = 0; j < H[i]; j++ ) printf( (j < H[r]) ? "#" : "." ); printf("\n"); 0048 } 0049 for ( int i = t; i < n; i++ ) { 0050 printf("%3d:%4d : ", i, H[i]); 0051 for ( int j = 0; j < H[i]; j++ ) printf("."); printf("\n"); 0052 } 0053 0054 delete [] H; 0055 return 0; 0056 }