左神算法进阶班4_1画出楼的轮廓-白红宇

左神算法进阶班4_1画出楼的轮廓

阅读量：7065 次

发布时间：2019-06-28

本文共 3152 字，大约阅读时间需要 10 分钟。

【题目】

给定一个N行3列二维数组，每一行表示有一座大楼，一共有N座大楼。

所有大楼的底部都坐落在X轴上，每一行的三个值(a, b, c)代表每座大楼的从(a, 0)点开始，到(b, 0)点结束，高度为c。

输入的数据可以保证 a < b, 且a，b，c均为正数。大楼之间可以有重合。请输出整体的轮廓线。

例子：给定一个二维数组[[1, 3, 3], [2, 4, 4], [5, 6, 1]]

输出为轮廓线[[1, 2, 3], [2, 4, 4], [5, 6, 1]]

【题解】

[1, 2, 3]表示第1个数到第2个数的高度为3

[2, 4, 4]表示第2个数到第4个数的高度为4

将数组进行分解：

[1, 2, 3]分解为：[1, 3, 上][3, 3, 下]

然后将这些分解的数组按照第一个数进行排序从小到大

准备一个红黑树map, key为楼高 value为楼高值出现的次数

怎么知道是否产生轮廓了呢？

从初始化楼高0开始

当压入数据中为上者，则对相应楼高key值的value++

每压入一个数字，就查看map中的最高的楼高值【即map中最大的key】是否发生变化，

一旦发生变化了，则产生了轮廓，无论是上去还是下来

没有发生变化则没有产生轮廓

当压入数据为下，则对相应楼高key值的value--，value == 0则删除该条key记录

注意

当在同一个位置产生两条记录，比如在4的位置上有一个数据为下，和一个数据为上，你在预处理数据进行排序时，谁前谁后？

一般是标记为下者排在前面，因为此时记录为楼高变下，那么前面一定有楼高变为上的

在压入数据时，要记录每个数位置的最大高度

【代码】

1 #pragma once  2 #include 
     
        3 #include 
        4 #include 
       
          5 #include 
        
           6   7 using namespace std;  8       9 vector
         
          
           > printContour(vector
           
            
             >v) 10 { 11 vector
             
              
               >data;//存放预处理后的数据 12 vector
               
                
                 >res;//答案 13 map
                 
                  mh;//记录楼高 14 map
                  
                   mp;//记录位置 15 for (auto &a : v) 16 { 17 vector
                   
                    num(3, 0); 18 num[0] = a[0];//起始点 19 num[1] = a[2];//楼高 20 num[2] = 1;//楼高标记为上 21 data.push_back(num); 22 num[0] = a[1];//终止点 23 num[1] = a[2];//楼高 24 num[2] = 0;//楼高标记为下 25 data.push_back(num); 26 } 27 sort(data.begin(), data.end(), [](vector
                    
                     v1, vector
                     
                      v2) { return v1[0] == v2[0] ? v1[2] == 0 : v1[0] < v2[0]; }); 28 //排序规则，第一位数相同者，楼下者排前面，不相同，则小的排在前面 29 for (auto& a : data) 30 { 31 if (a[2])//楼标记为上 32 { 33 if (mh.find(a[1]) != mh.end())//该楼高存在 34 ++mh[a[1]];//该楼高存在，进行记录增加 35 else 36 mh[a[1]] = 1;//该楼高不存在，加入 37 } 38 else//标记为楼下 39 { 40 if (mh.find(a[1]) != mh.end())//该楼高存在 41 { 42 if (mh[a[1]] == 1)//该楼高记录只有一个 43 mh.erase(a[1]);//删除该条记录 44 else 45 --mh[a[1]];//该楼高记录减一 46 } 47 } 48 49 if (mh.empty())//当楼高记录为0时，即中间有位置没有楼存在 50 mp[a[0]] = 0;//则标记该位置的楼高为0 51 else 52 mp[a[0]] = (--mh.end())->first;//其存在楼的地方采用最高楼记录 53 } 54 55 int start, height; 56 start = height = 0; 57 for (auto &a : mp)//遍历记录 58 { 59 int p = a.first;//位置 60 int h = a.second;//楼高 61 if (height != h)//楼高发生变化，那么就产生楼的轮廓了 62 { 63 if (height != 0) 64 { 65 vector
                      
                       temp(3, 0); 66 temp[0] = start; 67 temp[1] = p; 68 temp[2] = height; 69 res.push_back(temp); 70 } 71 start = p;//重新记录 72 height = h; 73 } 74 } 75 76 return res; 77 } 78 79 80 void Test() 81 { 82 vector
                       
                        
                         >v; 83 v = { { 1,3,3}, { 2,4,4}, { 5,6,1}}; 84 v = printContour(v); 85 for (auto &a : v) 86 { 87 for (auto b : a) 88 cout << b << " "; 89 cout << endl; 90 } 91 cout << "///" << endl; 92 v = { { 1,5,4}, { 2,3,3}, { 4,7,1},{ 6,9,5},{ 8,10,2}}; 93 v = printContour(v); 94 for (auto &a : v) 95 { 96 for (auto b : a) 97 cout << b << " "; 98 cout << endl; 99 }100 cout << "///" << endl;101 v = { { 1,3,3}, { 2,4,4}, { 5,6,1} };102 v = printContour(v);103 for (auto &a : v)104 {105 for (auto b : a)106 cout << b << " ";107 cout << endl;108 }109 cout << "///" << endl;110 v = { { 1,4,2},{ 2,9,1},{ 3,6,3},{ 5,8,4},{ 7,10,5}};111 v = printContour(v);112 for (auto &a : v)113 {114 for (auto b : a)115 cout << b << " ";116 cout << endl;117 }118 cout << "///" << endl;119 120 }