Problem Statement
The citizens of Byteland want to build N new buildings.
The new buildings will all stand in a line and they will be labeled 1 through N, in order.
The city regulations impose some restrictions on the heights of the new buildings.
You are given the parameters used in these restrictions: two
- The height of each building must be a nonnegative integer.
- The height of building 1 must be 0.
- The absolute value of the difference between any two adjacent buildings must be at most 1.
- For each valid i, the height of building x[i] must be t[i] or less.
Given these restrictions, the citizens of Byteland want to build a building that will be as tall as possible. Return the largest possible height some of the N buildings may have.
Definition
- Class:
- BuildingTowersEasy
- Method:
- maxHeight
- Parameters:
- int, int[], int[]
- Returns:
- int
- Method signature:
- int maxHeight(int N, int[] x, int[] t)
- (be sure your method is public)
Constraints
- N will be between 1 and 100,000, inclusive.
- x will contain between 0 and min(N,50) elements, inclusive.
- t will have exactly the same number of elements as x.
- Each element of x will be between 1 and N, inclusive.
- x[i] < x[i+1] for all valid i.
- Each element of t will be between 0 and 100,000, inclusive.
Examples
10
{3,8}
{1,1}
Returns: 3
In this case we are going to build 10 buildings. We have two constraints: the height of building 3 can be at most 1, and the height of building 8 can also be at most 1. The tallest possible new building in this city can have height 3. One optimal skyline looks as follows: {0,1,1,2,3,3,2,1,1,0}.
100000
{}
{}
Returns: 99999
There are no additional constraints so, for each valid i, the height of building i can be (i-1).
2718
{1,30,400,1300,2500}
{100000,100000,100000,100000,100000}
Returns: 2717
20
{4,7,13,15,18}
{3,8,1,17,16}
Returns: 8
447
{32,35,55,60,61,88,91,97,128,151,181,186,192,196,198,237,259,268,291,314,341,367,389,390,391,428,435}
{81,221,172,641,25,953,330,141,123,440,692,394,200,649,78,726,50,810,501,4,216,407,2,172,0,29,14}
Returns: 120
97638
{8,1749,4550,5388,6752,7089,9737,14891,16671,16821,17691,19753,24589, 25348,30114,32213,34376,36467,37699,41490,44784,44893,57316,58275,58567, 61122,61489,63195,64776,65905,68788,69908,72853,78152,78784,82779,84488, 86277,88611,92793,93214,97583}
{16610,6,497,14,42892,31,79,1203,518,31147,597,7846,1396,8309,12,14,1148, 433,23693,13,1939,244,19,46,27,611,412,10,27023,19141,34,15667,588,10,229, 83,390,14,38441,16021,4,39386}
Returns: 6343
462
{19,24,85,105,156,166,181,182,225,247,360,395,408,413,419,429,437,452}
{10,19,703,661,135,427,68,12,195,498,328,109,346,189,728,411,60,248}
Returns: 163
664
{21,41,47,105,148,201,230,261,270,297,359,376,400,432,438,445,495,499,597,630}
{710,0,506,8,485,770,348,5,344,0,245,34,70,3,146,255,69,556,92,690}
Returns: 159
942
{42,48,50,73,83,85,92,97,165,241,277,297,305,449,533,656,658,786,787,893}
{1,825,637,27,126,890,73,259,391,273,40,74,11,441,22,32,877,10,48,299}
Returns: 166
979
{56,70,72,93,98,110,117,138,150,194,274,280,290,300,349,359,382,398,444,457,495,508,521,607,611,633,667,692,712,736,794,802,812,853,918,923,925,934,951,971}
{31,36,417,21,128,39,6,574,189,480,7,205,91,86,177,820,448,456,760,0,605,129,577,280,953,137,37,13,59,250,186,979,605,615,912,69,310,586,187,63}
Returns: 156
22262
{2269,2414,2519,3382,3635,3801,6133,7157,9831,9927,10023,10841,11080,11594,12719,12853,13831,14229,14617,14832,15204,16578,16720,16783,16964,17029,17154,17456,18294,18939,20376,21105,21985}
{14,44719,24349,173,2,6,54286,379,1293,256,6133,6,1,317,2,1,23,95905,56671,50454,17,1,16972,5,44447,22,39,1,1918,1,1,4217,1641}
Returns: 1887
2201
{5,51,160,229,310,377,406,492,528,535,549,593,600,692,701,746,836,848,914,1002,1084,1120,1132,1142,1145,1253,1266,1282,1305,1328,1336,1344,1515,1529,1566,1611,1612,1613,1774,1795,1861,2045,2048,2142,2194}
{2772,11742,39,1743,1096,153,9,12,8936,34,463,650,34,1,6,4764,73101,11,139,1,5096,51,2434,1284,62645,6,55657,326,18,1,319,637,333,6,33420,14,5,13,7,56,10211,1497,5439,5,1031}
Returns: 190
36855
{1716,3413,5646,5790,6538,6634,8366,8590,10810,11494,12856,15581,16559,18272,19005,19157,21950,25246,27577,29626,29770,29823,30296,31645,33500,33506,34062,35146}
{3,10302,10,1658,1,455,1,11,28,1,34688,2306,8,1,13,21,42,362,53,22454,8,4,1,147,29,6275,767,429}
Returns: 2537
10806
{1304,1372,1997,2160,2510,2579,3375,4131,4205,5143,5591,5637,6583,6656,7182,7392,7728,7895,8032,8925,9064,9433,9667,9940,10058,10438,10596}
{5795,3,28,4837,30608,19,18944,25,44,111,965,1,933,1,26,21568,4,5,17,80,3,9,552,313,81817,16,516}
Returns: 798
90425
{2414,4417,4749,5549,5624,11318,20145,27184,29806,34221,40329,41293,46072,46438,47729,51838,51962,57423,59604,64512,68473,68482,69928,72382,76538,77850,80674,83168,84398,86416,88669,89386,90237}
{49,501,1,4,164,513,23003,3,1,538,21,58926,1,1,15726,869,1,86890,664,52,53402,60,41452,128,244,4117,2324,1,1,270,336,176,3}
Returns: 8191
39482
{605,873,909,1346,3021,4693,4919,4939,5856,7863,10252,11107,11165,11939,12319,15285,15617,18284,18687,19781,20808,21186,21477,21528,21997,24532,25294,25642,26032,26225,27308,27354,27712,28463,29151,29472,30560,31055,32071,32867,33277,33294,33522,33779,34976,35959,36501,36821,39393}
{58,2528,476,45,6,23,1,95,18656,4,77,290,32155,4329,5,12,4031,53656,69933,193,19,19,31043,3249,4239,9,5,74077,184,73,109,12256,9705,84620,17675,6483,81243,2,5213,18,1,3,39,2538,62,162,2160,2294,5755}
Returns: 3685
63976
{1280,7211,7535,8397,11446,11837,12475,13521,16639,17237,17247,17843,18519,19942,20015,20229,21656,21987,22575,24439,26236,27890,28975,35462,37738,41587,43125,44177,44342,45367,46012,47444,47723,48299,52185,53436,53973,54951,55229,56907,57987,58277,60763,61361}
{89929,1,2,1,2,1,111,3,12,45958,2665,334,1,6,128,31474,5,1892,32940,34,9,21,31,8,97,115,3,6279,194,2541,99,20,54902,34,1599,72,34,227,96314,41,99545,9,94505,4}
Returns: 3605
70351
{777,882,1674,2433,5032,5819,5860,6344,9598,19838,20317,20379,22781,23143,24451,24725,25284,25549,25888,27830,28744,28894,31442,33513,38681,38814,42249,42525,45243,46995,47307,49628,50293,50649,51103,53418,53453,53646,53702,53825,57316,59294,65956,68498}
{4,31,654,19,12,17,631,128,8548,3,13013,451,7751,2,3,492,1,33,9987,73435,843,2,93,4,16,30,17,2013,371,1,666,10,43543,39144,1337,29768,2,63739,10334,1,51,30,14,3151}
Returns: 6812
27071
{2580,3236,3471,3930,6501,6605,9228,9426,14791,14893,15386,15499,16172,16644,16670,17555,18634,19576,19599,19746,21440,21447,23315,24935,25439,26637,26715,26819}
{1,5,619,845,25400,51975,420,4,12393,30,137,667,8,722,78278,1,50,291,170,90,18663,27671,271,48,55,2,1,12781}
Returns: 3099
25072
{150,206,582,807,1000,1276,1964,3645,3655,4396,4572,4575,4699,5059,5356,5693,8071,8320,8740,8781,9708,10132,10204,10257,11008,11385,11917,14237,14547,14660,15087,15167,15845,16297,20924,21378,21922,22725,24483,24910,24923}
{70550,24146,9118,67139,5056,10667,67,1268,651,24987,1923,18537,24404,6648,10530,3907,204,32550,91725,34896,2648,49884,43546,35905,66247,65183,4906,8974,7885,1966,53,85364,37422,79468,4046,15328,93634,36878,3734,34672,23819}
Returns: 5669
63391
{1026,1477,1497,2701,3768,3995,4325,4701,6089,6162,6686,7664,8267,9153,12959,14382,15955,16035,17913,21257,22724,22793,24718,24856,30589,31090,31867,31995,32355,36003,36527,36676,37142,39080,39684,40749,41212,44221,49127,49526,49860,52028,52880,53049,55345,55591,58988,59744,59893,60245}
{30066,87897,2496,8290,52363,21755,8862,32935,68007,2073,344,65972,96691,29503,72613,13889,12154,7302,31,31463,39698,73146,91155,37953,2436,1323,43866,14133,29529,66750,46263,6550,97436,270,51473,61140,1643,34196,1020,8623,18736,35026,29128,35106,68,38329,36087,6034,92749,8825}
Returns: 8114
72621
{955,2577,3798,5685,6445,6973,9734,11374,11766,12205,13124,13276,13827,14832,16322,18960,20141,21099,24323,26596,26862,27525,29829,33151,36232,36297,36394,41902,41926,42335,42712,44626,44820,45109,49587,52043,54937,55307,57413,57661,62097,62989,65905,68478,68643,69576,69908,71244,71992,72012}
{222,16797,858,11913,27398,78676,32816,85506,41731,8775,2634,12533,8902,77237,70031,35671,34373,23467,9423,32962,25307,46388,4186,461,5734,94247,80865,1319,1997,99832,97265,2755,81855,59934,4702,4259,51365,66661,15950,3469,48838,72488,34797,33133,3697,1525,50816,34483,1787,44157}
Returns: 11561
60459
{779,938,3370,4612,6886,7853,8420,14530,15227,15728,16500,18171,21295,21441,22192,26765,26925,27915,28377,29516,33102,35049,35355,35529,37324,37593,37915,38644,39249,42231,43279,44783,45182,47732,49039,49594,51911,52335,53119,53213,56289}
{8424,8166,5697,21181,21777,8780,65091,88483,30136,55683,87419,21498,32912,25340,3512,24235,23823,79778,14931,16280,43424,9489,81941,17608,15867,69841,67557,24396,89995,34551,79113,74631,21622,73516,40529,10460,16606,50636,31072,1759,17201}
Returns: 14706
13399
{46,1195,1669,1841,2161,2238,2482,2601,2623,2721,3415,4057,4950,5102,6717,6765,7585,7669,7827,8833,9453,9575,9784,10406,11407,11843,11884,11886,12847,12945,12973}
{28481,14958,486,14738,4732,53868,16684,98809,22192,9390,29496,3493,24758,11711,7946,87482,14355,94454,13658,35353,40336,914,85883,793,21768,1262,29790,45522,2274,31392,77496}
Returns: 4653
88894
{1165,11041,13355,20448,22008,26337,30807,30993,34488,35366,40725,41168,42479,42710,45172,45220,45254,47053,48480,52589,56532,59088,61163,64711,68695,73610,74958,75306,77134,78063,81231,83456,84588}
{44854,71161,61362,29427,84088,68130,96407,18479,85472,74606,31062,31275,63148,97802,80373,25191,95434,84334,35287,89654,47078,63907,56468,76770,69495,79571,67184,69965,92877,98851,93617,24448,31252}
Returns: 43937
98615
{104,243,298,4491,5494,8391,12398,12744,16926,18611,19090,29509,30758,31333,41537,42199,42574,43690,46483,49201,50340,51929,52102,55340,55608,56224,56409,58908,59477,62535,63502,68575,71433,71927,72563,73011,73128,74694,75102,76400,84533,85578,86020,88209,90795,91016,95505,96420,96970,96991}
{36517,6333,37366,25789,66155,37221,86732,7893,27827,548,20147,13667,3172,83527,55570,99306,96484,67587,44067,62750,82242,42493,8087,34443,18428,91178,54662,11574,95468,69920,55632,28399,79733,20280,77739,31177,27870,14167,14285,5216,93599,51486,16998,83689,22190,972,51889,53090,29458,99175}
Returns: 17141
6097
{34,131,186,227,265,408,539,830,1537,1802,1995,2112,2273,2355,2691,2745,2937,2989,3025,3163,3278,3309,3424,3604,3691,3766,3771,3907,3915,4469,4492,4672,4979,5251,5395,5546,5605,5849,5948,6096}
{34006,41312,53558,86310,71539,30445,89143,66177,4111,20269,76575,29213,87177,48215,61548,80578,52722,89351,73371,60173,79934,72788,58630,21926,4043,8816,20670,18764,99436,63790,9257,21758,9202,53470,92381,49652,57396,12341,7893,35878}
Returns: 6096
72653
{2119,5657,8916,9670,10299,12173,15307,18512,20066,26510,29294,30342,33699,34086,34700,36682,37593,39205,43273,44345,45238,46197,47601,50435,52330,60199,61018,65199,66974,67178,67592,67912,68674,72251}
{88903,25212,74102,33080,51324,13880,44412,12477,33654,35481,23266,77903,85252,69110,64831,88510,2864,71364,95558,37157,32061,85683,39156,92261,8100,5071,72625,80302,66360,49708,81419,79170,22915,64045}
Returns: 17525
53851
{2544,3346,3350,7848,7878,9459,10845,11420,11533,12064,13110,13637,14378,16812,17488,18411,19329,22904,23682,23706,24281,24630,25020,25254,25344,25458,26916,29382,29725,29981,30096,30312,31227,31420,35471,37240,39823,40734,40885,41119,41208,43890,44094,46587,48392,49194,49446,49838,50645,53692}
{10816,66753,12117,67030,38336,41631,78642,85592,73535,42195,20392,76025,15500,9427,19605,63723,66910,18232,75398,60959,12485,93305,4123,94630,78949,92527,19792,1800,62295,34032,70615,73888,20715,15806,96868,42194,22277,52585,92588,62385,5295,33828,99000,73614,56307,88626,31128,79159,35651,28727}
Returns: 17938
1513
{1,2,3,4,5,6,7,8,9,10,11,12,13,34,35,38,59,78,80,95,96,121,142,213,583,635,736,751,793,1187}
{77300,19673,36382,43968,25738,78816,57938,96166,61464,23061,55880,34162,6131,37754,16903,35494,37439,88300,38399,86724,20832,30253,31327,87753,3129,82663,69267,8711,7395,92456}
Returns: 1512
66553
{1,2,3,5,9,13,23,79,120,134,142,315,467,514,569,968,1342,1580,2055,2806,3081,3216,7378,7516,10991,12716,23219,23681,25013,30418,47093,59521}
{27033,23104,26079,56384,58709,21983,6307,55113,11702,52381,88340,52618,22008,22542,44774,98662,79040,11824,40204,25232,24961,26966,56931,5532,78301,93704,64359,29079,53982,56873,72782,94372}
Returns: 64569
24246
{2,3,4,5,6,7,8,16,18,22,27,63,134,230,274,323,331,464,684,1060,1466,2642,3208,4343,6363,7313,7476}
{65708,94026,88956,67656,29552,56605,74979,93065,47656,84566,48903,71485,70288,50801,37301,64042,80541,79053,38208,22229,91585,7891,78050,90020,40493,36919,79226}
Returns: 24245
17683
{1,2,3,4,5,6,7,8,13,16,23,40,41,46,48,79,87,133,148,297,364,411,863,1893,2745,3225,8007,9958}
{74942,63948,47260,74891,54088,92708,84322,97292,75358,40992,17899,29808,59958,42887,51304,87751,21086,63825,76221,16091,82818,78657,41649,79810,68488,46060,25977,63315}
Returns: 17682
43146
{1,3,5,7,18,19,28,37,42,45,60,62,84,100,114,140,161,171,219,302,937,1255,1667,3208,3402,3722,4023,5060,20208,20988,25748,28761,39849,41168}
{97951,2605,88835,70563,97304,38136,25592,91145,55176,65569,97695,19037,30761,7323,37790,48285,28157,25601,55099,54183,60403,23166,1190,45712,82074,68031,60616,33529,82825,17857,64079,73154,67540,66434}
Returns: 40015
10787
{195,376,1744,2311,2963,3787,3804,3846,4120,4652,5086,5307,5612,5630,6738,6895,6930,7172,7321,7472,7789,8247,8767,8847,9219,9392,10062,10495,10554}
{61,60,8,27,12,25,99,11,11,23,25,48,4,70,100,5,66,41,8,29,88,36,100,60,1,75,76,69,12}
Returns: 718
59969
{862,1900,2628,3321,3641,5305,6096,7538,8400,13453,15153,15534,15590,21108,21930,22992,23311,26110,26920,27698,28097,28544,30064,33067,34821,35386,35852,36780,37601,37727,38963,39506,40093,42684,42943,42997,46916,47135,49061,50966,52475,53191,54993,56069,56120,56786,57637,59221}
{71,3,11,77,7,47,78,88,17,100,55,5,15,89,55,80,25,63,1,68,12,7,23,98,89,26,22,17,7,44,92,41,27,100,35,33,81,82,80,12,83,97,21,33,39,34,88,77}
Returns: 2811
65149
{1609,2058,2845,2969,3528,4967,7156,8825,12932,15477,17885,19254,19836,21171,21378,23156,27589,28172,31202,31403,31662,38331,38934,40103,42301,44976,47039,47324,48549,51335,53551,54474,56139,60276,61137,63495,64394}
{2,23,20,41,12,57,46,37,91,77,37,49,28,57,33,79,99,88,50,57,73,4,94,65,21,33,5,14,83,96,96,87,21,23,92,45,71}
Returns: 3373
64839
{120,770,2806,4670,10488,10642,12215,13891,19358,19528,20919,23310,25655,27072,28042,28492,30847,31398,31436,33550,35704,35778,36148,36781,37063,37358,37825,37862,38003,41198,41859,42424,43902,46032,47939,48975,49693,51467,52472,53183,53587,54639,56639,57641,59069,61346,63367,64197}
{23,11,20,88,12,27,54,24,22,87,46,12,94,68,6,66,70,37,55,62,26,59,43,27,50,28,15,86,83,61,45,100,82,42,64,22,60,69,61,62,24,98,34,89,34,60,82,56}
Returns: 2959
1016
{28,49,77,159,185,202,222,225,240,297,311,338,346,349,353,400,442,527,555,651,656,672,678,695,741,764,772,825,831,876,913,935,942,944,970,981}
{99,76,4,29,53,81,94,79,91,65,57,54,94,45,42,100,38,1,66,70,24,7,52,47,49,73,94,41,99,54,19,39,3,12,16,39}
Returns: 106
85097
{3265,10595,11372,11754,13472,14518,14651,18906,22099,22921,25799,26617,28468,30167,37087,39157,39666,44709,45007,49079,57135,58644,64471,64882,71664,72430,72601,77617,80225,82697}
{34,1,75,66,40,69,1,3,9,3,11,26,1,691,83,1,10,799,6,143,3,26,1,3,8,67,22,1,4,10}
Returns: 4101
79612
{1200,3028,6229,6534,6562,9329,13512,14702,17412,17798,27858,28405,36903,39169,39887,40819,42168,43321,44065,47695,48461,48591,51822,63125,63261,63471,64908,69944,74607,75589,76115,76968}
{456,3,460,153,152,5,3,395,20,2,4,7,84,3,33,323,3,23,30,146,3,45,70,33,9,83,55,551,3,230,29,7}
Returns: 5703
9701
{535,742,907,1215,1805,1834,2231,2459,2494,2941,3598,4408,4906,5320,5620,5644,6448,6479,6643,6829,7064,7069,7293,8128,8240,8485,8871,8876,9023,9345,9411}
{7,11,76,168,4,6,41,6,2,536,64,1,5,1,748,166,6,6,2,298,1,8,136,53,44,1,1,15,112,507,2}
Returns: 585
93420
{4005,5533,7131,7902,12354,19354,25872,28579,31592,34086,35505,36169,37204,37611,42279,52596,54243,56553,57794,58587,65802,72733,73864,75871,75886,76538,78011,79511,80645,81325,82604,82873,84556,85238,86005,86212,86842,90019,90189,91749,92368}
{134,14,43,55,605,76,1,571,6,10,1,253,89,2,169,1,2,30,2,6,4,769,476,2,11,690,10,52,17,99,725,13,1,33,1,311,10,501,437,555,1}
Returns: 5243
27459
{642,1516,2279,2629,3041,3252,3326,3982,4094,4241,4562,5038,5513,6406,7217,7377,8886,10054,10855,12677,13842,14315,15153,15183,16120,16535,19138,19784,19925,20604,21310,22794,23008,23108,23182,24490,24527,25905,26561,26596,27258,27395}
{74,387,255,7,97,1,19,6,54,1,20,250,66,48,469,486,16,213,18,1,213,3,1,139,4,169,11,696,1,882,493,16,1,2,1,217,8,62,13,18,3,304}
Returns: 1391
100000
{50000, 70000 }
{50000, 10000 }
Returns: 40000
9
{9 }
{0 }
Returns: 4
100000
{100000 }
{1 }
Returns: 50000
1
{1 }
{100000 }
Returns: 0
447
{32, 35, 55, 60, 61, 88, 91, 97, 128, 151, 181, 186, 192, 196, 198, 237, 259, 268, 291, 314, 341, 367, 389, 390, 391, 428, 435 }
{81, 221, 172, 641, 25, 953, 330, 141, 123, 440, 692, 394, 200, 649, 78, 726, 50, 810, 501, 4, 216, 407, 2, 172, 0, 29, 14 }
Returns: 120
3
{3 }
{0 }
Returns: 1
27
{10, 14 }
{70, 68 }
Returns: 26
2
{2 }
{3 }
Returns: 1
2
{2 }
{2 }
Returns: 1
10
{2, 3, 4 }
{0, 3, 4 }
Returns: 8
5
{2, 4, 5 }
{9, 3, 0 }
Returns: 2
133
{14 }
{61 }
Returns: 132
2
{1, 2 }
{0, 0 }
Returns: 0
82
{20, 36, 52, 59, 60, 69, 82 }
{89, 165, 186, 33, 130, 128, 33 }
Returns: 45
9
{1, 2, 3, 4, 5, 6, 7, 8, 9 }
{0, 5, 0, 7, 0, 2, 4, 10, 8 }
Returns: 4