给定一个整数数组，计算 次阵列 （指不止一个的）正在严格增加的。 预期时间复杂度：O（n） 预期额外空间：O（1）
null
例如：
Input: arr[] = {1, 4, 3}Output: 1There is only one subarray {1, 4}Input: arr[] = {1, 2, 3, 4}Output: 6There are 6 subarrays {1, 2}, {1, 2, 3}, {1, 2, 3, 4} {2, 3}, {2, 3, 4} and {3, 4}Input: arr[] = {1, 2, 2, 4}Output: 2There are 2 subarrays {1, 2} and {2, 4}
我们强烈建议您在继续解决方案之前单击此处并进行练习。
A. 简单解决方案 就是 生成所有可能的子阵列 ，并对每个子阵列检查子阵列是否严格增加。最坏情况下，该解决方案的时间复杂度为O（n） 3. ).
A. 更好的解决方案 如果子阵arr[i:j]不是严格递增的，那么子阵arr[i:j+1]，arr[i:j+2]。。arr[i:n-1]不能严格地增加。以下是基于上述理念的节目。
C++
// C++ program to count number of strictly // increasing subarrays #include<bits/stdc++.h> using namespace std; int countIncreasing( int arr[], int n) { // Initialize count of subarrays as 0 int cnt = 0; // Pick starting point for ( int i=0; i<n; i++) { // Pick ending point for ( int j=i+1; j<n; j++) { if (arr[j] > arr[j-1]) cnt++; // If subarray arr[i..j] is not strictly // increasing, then subarrays after it , i.e., // arr[i..j+1], arr[i..j+2], .... cannot // be strictly increasing else break ; } } return cnt; } // Driver program int main() { int arr[] = {1, 2, 2, 4}; int n = sizeof (arr)/ sizeof (arr[0]); cout << "Count of strictly increasing subarrays is " << countIncreasing(arr, n); return 0; } |
JAVA
// Java program to count number of strictly // increasing subarrays class Test { static int arr[] = new int []{ 1 , 2 , 2 , 4 }; static int countIncreasing( int n) { // Initialize count of subarrays as 0 int cnt = 0 ; // Pick starting point for ( int i= 0 ; i<n; i++) { // Pick ending point for ( int j=i+ 1 ; j<n; j++) { if (arr[j] > arr[j- 1 ]) cnt++; // If subarray arr[i..j] is not strictly // increasing, then subarrays after it , i.e., // arr[i..j+1], arr[i..j+2], .... cannot // be strictly increasing else break ; } } return cnt; } // Driver method to test the above function public static void main(String[] args) { System.out.println( "Count of strictly increasing subarrays is " + countIncreasing(arr.length)); } } |
Python3
# Python3 program to count number # of strictly increasing subarrays def countIncreasing(arr, n): # Initialize count of subarrays as 0 cnt = 0 # Pick starting point for i in range ( 0 , n) : # Pick ending point for j in range (i + 1 , n) : if arr[j] > arr[j - 1 ] : cnt + = 1 # If subarray arr[i..j] is not strictly # increasing, then subarrays after it , i.e., # arr[i..j+1], arr[i..j+2], .... cannot # be strictly increasing else : break return cnt # Driver code arr = [ 1 , 2 , 2 , 4 ] n = len (arr) print ( "Count of strictly increasing subarrays is" , countIncreasing(arr, n)) # This code is contributed by Shreyanshi Arun. |
C#
// C# program to count number of // strictly increasing subarrays using System; class Test { static int []arr = new int []{1, 2, 2, 4}; static int countIncreasing( int n) { // Initialize count of subarrays as 0 int cnt = 0; // Pick starting point for ( int i = 0; i < n; i++) { // Pick ending point for ( int j = i + 1; j < n; j++) { if (arr[j] > arr[j - 1]) cnt++; // If subarray arr[i..j] is not strictly // increasing, then subarrays after it , // i.e., arr[i..j+1], arr[i..j+2], .... // cannot be strictly increasing else break ; } } return cnt; } // Driver Code public static void Main(String[] args) { Console.Write( "Count of strictly increasing" + "subarrays is " + countIncreasing(arr.Length)); } } // This code is contribute by parashar. |
PHP
<?php // PHP program to count number of // strictly increasing subarrays function countIncreasing( $arr , $n ) { // Initialize count of subarrays // as 0 $cnt = 0; // Pick starting point for ( $i = 0; $i < $n ; $i ++) { // Pick ending point for ( $j = $i +1; $j < $n ; $j ++) { if ( $arr [ $j ] > $arr [ $j -1]) $cnt ++; // If subarray arr[i..j] is // not strictly increasing, // then subarrays after it, // i.e., arr[i..j+1], // arr[i..j+2], .... cannot // be strictly increasing else break ; } } return $cnt ; } // Driver program $arr = array (1, 2, 2, 4); $n = count ( $arr ); echo "Count of strictly increasing " , "subarrays is " , countIncreasing( $arr , $n ); // This code is contribute by anuj_67. ?> |
Javascript
<script> // Javascript program to count number of strictly // increasing subarrays function countIncreasing(arr, n) { // Initialize count of subarrays as 0 let cnt = 0; // Pick starting point for (let i = 0; i < n; i++) { // Pick ending point for (let j = i + 1; j < n; j++) { if (arr[j] > arr[j - 1]) cnt++; // If subarray arr[i..j] is not strictly // increasing, then subarrays after it , i.e., // arr[i..j+1], arr[i..j+2], .... cannot // be strictly increasing else break ; } } return cnt; } // Driver code let arr = [ 1, 2, 2, 4 ]; let n = arr.length; document.write( "Count of strictly " + "increasing subarrays is " + countIncreasing(arr, n)); // This code is contributed by divyesh072019 </script> |
输出：
Count of strictly increasing subarrays is 2
上述解决方案的时间复杂度为O（m），其中m是输出中的子阵列数 这个问题和解决方案是由拉胡尔·阿格拉瓦尔提出的。
一 有效解决方案 可以在O（n）时间内计算子阵列。这个想法基于这样一个事实：长度为“len”的排序子数组将len*（len-1）/2添加到结果中。例如，{10,20,30,40}将结果加6。
C++
// C++ program to count number of strictly // increasing subarrays in O(n) time. #include<bits/stdc++.h> using namespace std; int countIncreasing( int arr[], int n) { int cnt = 0; // Initialize result // Initialize length of current increasing // subarray int len = 1; // Traverse through the array for ( int i=0; i < n-1; ++i) { // If arr[i+1] is greater than arr[i], // then increment length if (arr[i + 1] > arr[i]) len++; // Else Update count and reset length else { cnt += (((len - 1) * len) / 2); len = 1; } } // If last length is more than 1 if (len > 1) cnt += (((len - 1) * len) / 2); return cnt; } // Driver program int main() { int arr[] = {1, 2, 2, 4}; int n = sizeof (arr)/ sizeof (arr[0]); cout << "Count of strictly increasing subarrays is " << countIncreasing(arr, n); return 0; } |
JAVA
// Java program to count number of strictly // increasing subarrays class Test { static int arr[] = new int []{ 1 , 2 , 2 , 4 }; static int countIncreasing( int n) { int cnt = 0 ; // Initialize result // Initialize length of current increasing // subarray int len = 1 ; // Traverse through the array for ( int i= 0 ; i < n- 1 ; ++i) { // If arr[i+1] is greater than arr[i], // then increment length if (arr[i + 1 ] > arr[i]) len++; // Else Update count and reset length else { cnt += (((len - 1 ) * len) / 2 ); len = 1 ; } } // If last length is more than 1 if (len > 1 ) cnt += (((len - 1 ) * len) / 2 ); return cnt; } // Driver method to test the above function public static void main(String[] args) { System.out.println( "Count of strictly increasing subarrays is " + countIncreasing(arr.length)); } } |
Python3
# Python3 program to count number of # strictlyincreasing subarrays in O(n) time. def countIncreasing(arr, n): cnt = 0 # Initialize result # Initialize length of current # increasing subarray len = 1 # Traverse through the array for i in range ( 0 , n - 1 ) : # If arr[i+1] is greater than arr[i], # then increment length if arr[i + 1 ] > arr[i] : len + = 1 # Else Update count and reset length else : cnt + = ((( len - 1 ) * len ) / 2 ) len = 1 # If last length is more than 1 if len > 1 : cnt + = ((( len - 1 ) * len ) / 2 ) return cnt # Driver program arr = [ 1 , 2 , 2 , 4 ] n = len (arr) print ( "Count of strictly increasing subarrays is" , int (countIncreasing(arr, n))) # This code is contributed by Shreyanshi Arun. |
C#
// C# program to count number of strictly // increasing subarrays using System; class GFG { static int []arr = new int []{1, 2, 2, 4}; static int countIncreasing( int n) { int cnt = 0; // Initialize result // Initialize length of current // increasing subarray int len = 1; // Traverse through the array for ( int i = 0; i < n-1; ++i) { // If arr[i+1] is greater than // arr[i], then increment length if (arr[i + 1] > arr[i]) len++; // Else Update count and reset // length else { cnt += (((len - 1) * len) / 2); len = 1; } } // If last length is more than 1 if (len > 1) cnt += (((len - 1) * len) / 2); return cnt; } // Driver method to test the // above function public static void Main() { Console.WriteLine( "Count of strictly " + "increasing subarrays is " + countIncreasing(arr.Length)); } } // This code is contribute by anuj_67. |
PHP
<?php // PHP program to count number of strictly // increasing subarrays in O(n) time. function countIncreasing( $arr , $n ) { // Initialize result $cnt = 0; // Initialize length of // current increasing // subarray $len = 1; // Traverse through the array for ( $i = 0; $i < $n - 1; ++ $i ) { // If arr[i+1] is greater than arr[i], // then increment length if ( $arr [ $i + 1] > $arr [ $i ]) $len ++; // Else Update count and // reset length else { $cnt += ((( $len - 1) * $len ) / 2); $len = 1; } } // If last length is // more than 1 if ( $len > 1) $cnt += ((( $len - 1) * $len ) / 2); return $cnt ; } // Driver Code $arr = array (1, 2, 2, 4); $n = count ( $arr ); echo "Count of strictly increasing subarrays is " , countIncreasing( $arr , $n ); // This code is contribute by anuj_67 ?> |
Javascript
<script> // Javascript program to count number of strictly // increasing subarrays let arr = [1, 2, 2, 4]; function countIncreasing(n) { let cnt = 0; // Initialize result // Initialize length of current // increasing subarray let len = 1; // Traverse through the array for (let i = 0; i < n-1; ++i) { // If arr[i+1] is greater than // arr[i], then increment length if (arr[i + 1] > arr[i]) len++; // Else Update count and reset // length else { cnt += (((len - 1) * len) / 2); len = 1; } } // If last length is more than 1 if (len > 1) cnt += (((len - 1) * len) / 2); return cnt; } document.write( "Count of strictly " + "increasing subarrays is " + countIncreasing(arr.length)); </script> |
输出：
Count of strictly increasing subarrays is 2
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
