0001 #include <cstdlib>
0002 #include <ctime>
0003 #include <cstdio>
0004 #include <typeinfo>
0005 
0006 uint64_t mr1Pass(uint64_t H[], Rank n); //借助一个栈：O(n)
0007 uint64_t mr2Pass(uint64_t H[], Rank n); // 借助两个栈：O(n)
0008 uint64_t mrBrute(uint64_t H[], Rank n); // 蛮力：O(n^2)
0009 
0010 Rank ms = -1, mr = -1, mt = -1; //最大矩形 = H[mr]*(mt-ms)
0011 
0012 int main(int argc, char* argv[]) { //直方图中的最大矩形
0013    uint64_t* H; Rank 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 uint64_t[n = argc - 1];
0016       for (Rank i = 0; i < n; i++)
0017          H[i] = atoi(argv[i+1]);
0018    } else { //随机生成
0019       srand(31415926); //srand((uint32_t) time(nullptr)); //随机种子
0020       H = new uint64_t[1 + (n = rand()%128)];
0021       for (Rank i = 0; i < n; i++)
0022          H[i] = rand() % 128;
0023    }
0024 
0025    uint64_t mrbrute = mrBrute(H, n);
0026    printf("MaxRect Brute-Force  : %I64d = %I64d x [%d,%d)\n", mrbrute, H[mr], ms, mt);
0027    uint64_t mr2pass = mr2Pass(H, n);
0028    printf("MaxRect by 2-pass scan : %I64d = %I64d x [%d,%d)\n", mr2pass, H[mr], ms, mt);
0029    uint64_t mr1pass  = mr1Pass(H, n);
0030    printf("MaxRect by 1-pass scan : %I64d = %I64d x [%d,%d)\n", mr1pass, H[mr], ms, mt);
0031 
0032    for (Rank i = 0; i < ms; i++) {
0033       printf("%20I64d [%3d]: ", H[i], i);
0034       for (int j = 0; j < H[i]; j++) printf("."); printf("\n");
0035    }
0036    for (Rank i = ms; i < mr; i++) {
0037       printf("%20I64d [%3d]: ", H[i], i);
0038       for (int j = 0; j < H[i]; j++) printf((j < H[mr]) ? "#" : "."); printf("\n");
0039    }
0040    {
0041       printf("%20I64d [%3d]: ", H[mr], mr);
0042       for (int j = 0; j < H[mr]; j++) printf("O"); printf("\n");
0043    }
0044    for (Rank i = mr+1; i < mt; i++) {
0045       printf("%20I64d [%3d]: ", H[i], i);
0046       for (int j = 0; j < H[i]; j++) printf((j < H[mr]) ? "#" : "."); printf("\n");
0047    }
0048    for (Rank i = mt; i < n; i++) {
0049       printf("%20I64d [%3d]: ", H[i], i);
0050       for (int j = 0; j < H[i]; j++) printf("."); printf("\n");
0051    }
0052 
0053    delete[] H;
0054    return 0;
0055 } //main