0001 #include <cstdlib>
0002 #include <ctime>
0003 #include <cstdio>
0004 using Rank = unsigned int;
0005 
0006 __int64 mr_STACK ( int H[], Rank n, Rank& r, Rank& s, Rank& t ); //借助一个栈：O(n)
0007 __int64 mr_STACKS( int H[], Rank n, Rank& r, Rank& s, Rank& t ); //借助两个栈：O(n)
0008 __int64 mr_BRUTE ( int H[], Rank n, Rank& r, Rank& s, Rank& t ); //蛮力：O(n^2)
0009 
0010 /******************************************************************************************
0011  * 直方图中的最大矩形
0012  ******************************************************************************************/
0013 int main( int argc, char* argv[] ) {
0014    int* H; Rank n; //宽度为n的直方图
0015    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
0016       H = new int[ n = argc -1 ];
0017       for ( Rank i = 0; i < n; i++ )
0018          H[i] = atoi( argv[i+1] );
0019    } else { //随机生成
0020       srand ( ( unsigned int ) time ( NULL ) );
0021       H = new int[ 1 + ( n = rand() % 128 ) ];
0022       for ( Rank i = 0; i < n; i++ )
0023          H[i] = rand() % 128;
0024    }
0025 
0026    Rank r, s, t; //最大矩形：H[r] x [s, t)
0027    __int64 mrBrute = mr_BRUTE( H, n, r = -1, s = -1, t = -1 );
0028    printf( "MaxRect Brute-Force  : %I64d = %d x [%d,%d)\n", mrBrute, H[r], s, t );
0029    __int64 mrStacks = mr_STACKS( H, n, r = -1, s = -1, t = -1 );
0030    printf( "MaxRect using STACKS : %I64d = %d x [%d,%d)\n", mrStacks, H[r], s, t );
0031    __int64 mrStack  = mr_STACK ( H, n, r = -1, s = -1, t = -1 );
0032    printf( "MaxRect using STACK  : %I64d = %d x [%d,%d)\n", mrStack, H[r], s, t );
0033 
0034    for ( Rank i = 0; i < s; i++ ) {
0035       printf("%3d:%4d : ", i, H[i]);
0036       for ( int j = 0; j < H[i]; j++ ) printf("."); printf("\n");
0037    }
0038    for ( Rank i = s; i < r; i++ ) {
0039       printf("%3d:%4d : ", i, H[i]);
0040       for ( int j = 0; j < H[i]; j++ ) printf( (j < H[r]) ? "#" : "." ); printf("\n");
0041    }
0042    {
0043       printf("%3d:%4d : ", r, H[r]);
0044       for ( int j = 0; j < H[r]; j++ ) printf("O"); printf("\n");
0045    }
0046    for ( Rank i = r+1; i < t; i++ ) {
0047       printf("%3d:%4d : ", i, H[i]);
0048       for ( int j = 0; j < H[i]; j++ ) printf( (j < H[r]) ? "#" : "." ); printf("\n");
0049    }
0050    for ( Rank i = t; i < n; i++ ) {
0051       printf("%3d:%4d : ", i, H[i]);
0052       for ( int j = 0; j < H[i]; j++ ) printf("."); printf("\n");
0053    }
0054 
0055    delete [] H;
0056    return 0;
0057 }