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