数组值三角形排列的最大高度-yiteyi-C++库

给定一个数组，我们需要从数组值中找出三角形的最大高度，这样每一个（i+1）级包含更多的元素，并且与前一级的总和更大。 例如：

null

Input : a = { 40, 100, 20, 30 }Output : 2Explanation : We can have 100 and 20 at the bottom level and either 40 or 30 at the upper level of the pyramidInput : a = { 20, 20, 10, 10, 5, 2 }Output : 3

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

首先，乍一看，我们可能需要查看数组值。但事实并非如此。这是这个问题中棘手的部分。在这里，我们不必关心数组值，因为我们可以将数组中的任何元素安排为满足这些条件的三角形值。即使所有元素都相等，比如array={3,3,3,3,3}，我们也可以得到解。我们可以在底部放置两个3，在顶部放置一个3，或者在底部放置三个3，在顶部放置两个3。你可以举自己的任何例子，你总能找到一个解决方案，将它们安排在一个配置中。所以，如果我们的最大高度是2，那么我们应该在底部至少有2个元素，在顶部至少有一个元素，这意味着我们应该至少有3个元素（2*（2+1）/2）。类似地，对于3作为高度，数组中至少应有6个元素。因此，我们最终的解决方案只是基于这样一个逻辑：如果我们有最大高度 H 那么我们的金字塔可能 （h*（h+1））/2 数组中必须存在元素。 以下是上述方法的实施情况：

C++

                         // C++ program to find the maximum height                       
                         // of Pyramidal Arrangement of array values                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         int                                     MaximumHeight(                                     int                                     a[],                                     int                                     n)                       
                         {                       
                                                 int                                     result = 1;                       
                                                 for                                     (                                     int                                     i = 1; i <= n; ++i) {                       
           
                                                 // Just checking whether ith level                       
                                                 // is possible or not if possible                       
                                                 // then we must have atleast                       
                                                 // (i*(i+1))/2 elements in the                       
                                                 // array                       
                                                 long                                     long                                     y = (i * (i + 1)) / 2;                       
           
                                                 // updating the result value                       
                                                 // each time                       
                                                 if                                     (y < n)                       
                                                 result = i;                       
                                   
                                                 // otherwise we have exceeded n value                       
                                                 else                       
                                                 break                                     ;                       
                                                 }                       
                                                 return                                     result;                       
                         }                       
           
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 40, 100, 20, 30 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 cout << MaximumHeight(arr, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find                       
                         // the maximum height of                       
                         // Pyramidal Arrangement                       
                         // of array values                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                         static                                     int                                     MaximumHeight(                                     int                                     []a,                       
                                                 int                                     n)                       
                         {                       
                                   
                                                 int                                     result =                                     1                                     ;                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= n; ++i)                       
                                                 {                       
           
                                                 // Just checking whether                       
                                                 // ith level is possible                       
                                                 // or not if possible then                       
                                                 // we must have atleast                       
                                                 // (i*(i+1))/2 elements                       
                                                 // in the array                       
                                                 int                                     y = (i * (i +                                     1                                     )) /                                     2                                     ;                       
           
                                                 // updating the result                       
                                                 // value each time                       
                                                 if                                     (y < n)                       
                                                 result = i;                       
                                   
                                                 // otherwise we have                       
                                                 // exceeded n value                       
                                                 else                       
                                                 break                                     ;                       
                                                 }                       
                                                 return                                     result;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main (String[] args)                       
                         {                       
                                                 int                                     []arr = {                                     40                                     ,                                     100                                     ,                                     20                                     ,                                     30                                     };                       
                                                 int                                     n = arr.length;                       
                                                 System.out.println(MaximumHeight(arr, n));                       
                         }                       
                         }                       
           
                         // This code is contributed by ajit                       

Python3

                         # Python program to find the                       
                         # maximum height of Pyramidal                       
                         # Arrangement of array values                       
           
                         def                                     MaximumHeight(a, n):                       
                                                 result                                     =                                     1                       
           
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n):                       
                                   
                                                 # Just checking whether ith level                       
                                                 # is possible or not if possible                       
                                                 # then we must have atleast                       
                                                 # (i*(i+1))/2 elements in the array                       
                                                 y                                     =                                     (i                                     *                                     (i                                     +                                     1                                     ))                                     /                                     2                       
           
                                                 # updating the result                       
                                                 # value each time                       
                                                 if                                     (y < n):                       
                                                 result                                     =                                     i                       
                                   
                                                 # otherwise we have                       
                                                 # exceeded n value                       
                                                 else                                     :                       
                                                 break                       
           
                                                 return                                     result                       
           
                         # Driver Code                       
                         arr                                     =                                     [                                     40                                     ,                                     100                                     ,                                     20                                     ,                                     30                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         print                                     (MaximumHeight(arr, n))                       
           
                         # This code is contributed by                       
                         # Sanjit_Prasad                       

C#

                         // C# program to find                       
                         // the maximum height of                       
                         // Pyramidal Arrangement                       
                         // of array values                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                         static                                     int                                     MaximumHeight(                                     int                                     []a,                       
                                                 int                                     n)                       
                         {                       
                                                 int                                     result = 1;                       
                                                 for                                     (                                     int                                     i = 1; i <= n; ++i)                       
                                                 {                       
           
                                                 // Just checking whether                       
                                                 // ith level is possible                       
                                                 // or not if possible then                       
                                                 // we must have atleast                       
                                                 // (i*(i+1))/2 elements                       
                                                 // in the array                       
                                                 int                                     y = (i * (i + 1)) / 2;                       
           
                                                 // updating the result                       
                                                 // value each time                       
                                                 if                                     (y < n)                       
                                                 result = i;                       
                                   
                                                 // otherwise we have                       
                                                 // exceeded n value                       
                                                 else                       
                                                 break                                     ;                       
                                                 }                       
                                                 return                                     result;                       
                         }                       
           
                         // Driver Code                       
                         static                                     public                                     void                                     Main ()                       
                         {                       
                                                 int                                     []arr = {40, 100, 20, 30};                       
                                                 int                                     n = arr.Length;                       
                                                 Console.WriteLine(MaximumHeight(arr, n));                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by m_kit                       

PHP

                         <?php                       
                         // PHP program to find the maximum height                       
                         // of Pyramidal Arrangement of array values                       
           
                         function                                     MaximumHeight(                                     $a                                     ,                                     $n                                     )                       
                         {                       
                                                 $result                                     = 1;                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $n                                     ; ++                                     $i                                     )                       
                                                 {                       
           
                                                 // Just checking whether ith level                       
                                                 // is possible or not if possible                       
                                                 // then we must have atleast                       
                                                 // (i*(i+1))/2 elements in the                       
                                                 // array                       
                                                 $y                                     = (                                     $i                                     * (                                     $i                                     + 1)) / 2;                       
           
                                                 // updating the result value                       
                                                 // each time                       
                                                 if                                     (                                     $y                                     <                                     $n                                     )                       
                                                 $result                                     =                                     $i                                     ;                       
                                   
                                                 // otherwise we have                       
                                                 // exceeded n value                       
                                                 else                       
                                                 break                                     ;                       
                                                 }                       
                                                 return                                     $result                                     ;                       
                         }                       
           
                                                 // Driver Code                       
                                                 $arr                                     =                                     array                                     (40, 100, 20, 30);                       
                                                 $n                                     =                                     count                                     (                                     $arr                                     );                       
                                                 echo                                     MaximumHeight(                                     $arr                                     ,                                     $n                                     );                       
           
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
                         // Javascript program to find                       
                         // the maximum height of                       
                         // Pyramidal Arrangement                       
                         // of array values                       
                                                 function                                     MaximumHeight( a ,n)                       
                                                 {                       
           
                                                 let result = 1;                       
                                                 for                                     ( i = 1; i <= n; ++i) {                       
           
                                                 // Just checking whether                       
                                                 // ith level is possible                       
                                                 // or not if possible then                       
                                                 // we must have atleast                       
                                                 // (i*(i+1))/2 elements                       
                                                 // in the array                       
                                                 let y = (i * (i + 1)) / 2;                       
           
                                                 // updating the result                       
                                                 // value each time                       
                                                 if                                     (y < n)                       
                                                 result = i;                       
           
                                                 // otherwise we have                       
                                                 // exceeded n value                       
                                                 else                       
                                                 break                                     ;                       
                                                 }                       
                                                 return                                     result;                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 let arr = [ 40, 100, 20, 30 ];                       
                                                 let n = arr.length;                       
                                                 document.write(MaximumHeight(arr, n));                       
           
                         // This code is contributed by Rajput-Ji                       
                         </script>                       

输出：

时间复杂性： O（n） 空间复杂性： O（1） 我们可以在O（1）时间内解决这个问题。我们只需要找到最大值 i*（i+1）/2<=n .如果我们解这个方程，我们得到 地板（-1+sqrt（1+8*n））/2）

C++

                         // CPP program to find the maximum height                       
                         // of Pyramidal Arrangement of array values                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         int                                     MaximumHeight(                                     int                                     a[],                                     int                                     n)                       
                         {                       
                                                 return                                     floor                                     ((-1+                                     sqrt                                     (1+(8*n)))/2);                       
                         }                       
           
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 40, 100, 20, 30 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 cout << MaximumHeight(arr, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find the maximum height                       
                         // of Pyramidal Arrangement of array values                       
                         import                                     java.lang.*;                       
           
                         class                                     GFG {                       
                                   
                                                 static                                     int                                     MaximumHeight(                                     int                                     a[],                                     int                                     n)                       
                                                 {                       
                                                 return                                     (                                     int                                     )Math.floor((-                                     1                                     +                       
                                                 Math.sqrt(                                     1                                     + (                                     8                                     * n))) /                                     2                                     );                       
                                                 }                       
                                   
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] =                                     new                                     int                                     []{                                     40                                     ,                                     100                                     ,                                     20                                     ,                                     30                                     };                       
                                                 int                                     n = arr.length;                       
                                   
                                                 System.out.println(MaximumHeight(arr, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Smitha                       

Python3

                         # Python program to find the                       
                         # maximum height of Pyramidal                       
                         # Arrangement of array values                       
                         import                                     math                       
           
                         def                                     MaximumHeight(a, n):                       
                                                 return                                     (                                     -                                     1                                     +                                     int                                     (math.sqrt(                                     1                                     +                       
                                                 (                                     8                                     *                                     n))))                                     /                                     /                                     2                       
           
                         # Driver Code                       
                         arr                                     =                                     [                                     40                                     ,                                     100                                     ,                                     20                                     ,                                     30                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         print                                     (MaximumHeight(arr, n))                       
           
                         # This code is contributed by                       
                         # Sanjit_Prasad                       

C#

                         // C# program to find the maximum height                       
                         // of Pyramidal Arrangement of array values                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 static                                     int                                     MaximumHeight(                                     int                                     []a,                                     int                                     n)                       
                                                 {                       
                                                 return                                     (                                     int                                     )Math.Floor((-1 +                       
                                                 Math.Sqrt(1 + (8 * n))) / 2);                       
                                                 }                       
                                   
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []arr =                                     new                                     int                                     []{ 40, 100, 20, 30 };                       
                                                 int                                     n = 4;                       
                                   
                                                 Console.Write(MaximumHeight(arr, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Smitha                       

PHP

                         <?php                       
                         // PHP program to find                       
                         // the maximum height                       
                         // of Pyramidal Arrangement                       
                         // of array values                       
           
                         function                                     MaximumHeight(                                     $a                                     ,                                     $n                                     )                       
                         {                       
                                                 return                                     floor                                     ((-1 + sqrt(1 +                       
                                                 (8 *                                     $n                                     ))) / 2);                       
                         }                       
                                   
                                                 // Driver Code                       
                                                 $arr                                     =                                     array                                     (40, 100, 20, 30);                       
                                                 $n                                     =                                     count                                     (                                     $arr                                     );                       
                                                 echo                                     MaximumHeight(                                     $arr                                     ,                                     $n                                     );                       
           
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
                         // javascript program to find the maximum height                       
                         // of Pyramidal Arrangement of array values                       
                         function                                     MaximumHeight(a, n)                       
                         {                       
                                                 return                                     Math.floor((-1 + Math.sqrt(1 + (8 * n))) / 2);                       
                         }                       
           
                         // Driver code                       
                                                 let arr = [ 40, 100, 20, 30 ];                       
                                                 let n = arr.length;                       
                                                 document.write(MaximumHeight(arr, n));                       
                                   
                                                 // This code is contributed by gauravrajput1                       
           
                         </script>                       

输出：

时间复杂性： O（1） 空间复杂性： O（1）

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章