logo

TechCodeview

최대 요소가 k보다 큰 하위 배열 수

주어진 배열 N 요소와 정수 케이 . 이 작업은 K보다 큰 최대 요소를 가진 하위 배열의 개수를 찾는 것입니다.

예:  

Input : arr[] = {1 2 3} and k = 2.  
Output : 3  
All the possible subarrays of arr[] are   
{ 1 } { 2 } { 3 } { 1 2 } { 2 3 }   
{ 1 2 3 }.  
Their maximum elements are 1 2 3 2 3 3.  
There are only 3 maximum elements > 2.
Recommended Practice 하위 배열 수 시도해 보세요!

접근법 1: 최대 요소를 갖는 하위 배열 계산<= K and then subtracting from total subarrays.

아이디어는 최대 요소가 k보다 작거나 같은 하위 배열을 계산하는 것이 더 쉽기 때문에 문제에 접근하는 것입니다. 최대 요소가 k보다 작거나 같은 하위 배열의 수를 찾으려면 K보다 큰 모든 요소를 ​​제거하고 왼쪽 요소가 있는 하위 배열의 수를 찾으세요. 



위의 수를 찾으면 n*(n+1)/2에서 이를 빼서 필요한 결과를 얻을 수 있습니다. 크기가 n인 배열에는 n*(n+1)/2개의 하위 배열이 있을 수 있다는 점에 유의하세요. 따라서 최대 요소가 K보다 작거나 같은 하위 배열의 수를 찾아 n*(n+1)/2에서 빼면 답을 얻을 수 있습니다.

다음은 이 접근 방식의 구현입니다.

C++ 
// C++ program to count number of subarrays // whose maximum element is greater than K. #include    using namespace std; // Return number of subarrays whose maximum // element is less than or equal to K. int countSubarray(int arr[] int n int k) {  // To store count of subarrays with all  // elements less than or equal to k.  int s = 0;  // Traversing the array.  int i = 0;  while (i < n) {  // If element is greater than k ignore.  if (arr[i] > k) {  i++;  continue;  }  // Counting the subarray length whose  // each element is less than equal to k.  int count = 0;  while (i < n && arr[i] <= k) {  i++;  count++;  }  // Summing number of subarray whose  // maximum element is less than equal to k.  s += ((count * (count + 1)) / 2);  }  return (n * (n + 1) / 2 - s); } // Driven Program int main() {  int arr[] = { 1 2 3 };  int k = 2;  int n = sizeof(arr) / sizeof(arr[0]);  cout << countSubarray(arr n k);  return 0; }
Java 
// Java program to count number of subarrays // whose maximum element is greater than K. import java.util.*; class GFG {  // Return number of subarrays whose maximum  // element is less than or equal to K.  static int countSubarray(int arr[] int n int k)  {  // To store count of subarrays with all  // elements less than or equal to k.  int s = 0;  // Traversing the array.  int i = 0;  while (i < n) {  // If element is greater than k ignore.  if (arr[i] > k) {  i++;  continue;  }  // Counting the subarray length whose  // each element is less than equal to k.  int count = 0;  while (i < n && arr[i] <= k) {  i++;  count++;  }  // Summing number of subarray whose  // maximum element is less than equal to k.  s += ((count * (count + 1)) / 2);  }  return (n * (n + 1) / 2 - s);  }  // Driver code  public static void main(String[] args)  {  int arr[] = { 1 2 3 };  int k = 2;  int n = arr.length;  System.out.print(countSubarray(arr n k));  } } // This code is contributed by Anant Agarwal.
Python3 
# Python program to count # number of subarrays # whose maximum element # is greater than K. # Return number of # subarrays whose maximum # element is less than or equal to K. def countSubarray(arr n k): # To store count of # subarrays with all # elements less than # or equal to k. s = 0 # Traversing the array. i = 0 while (i < n): # If element is greater # than k ignore. if (arr[i] > k): i = i + 1 continue # Counting the subarray # length whose # each element is less # than equal to k. count = 0 while (i < n and arr[i] <= k): i = i + 1 count = count + 1 # Summing number of subarray whose # maximum element is less # than equal to k. s = s + ((count*(count + 1))//2) return (n*(n + 1)//2 - s) # Driver code arr = [1 2 3] k = 2 n = len(arr) print(countSubarray(arr n k)) # This code is contributed # by Anant Agarwal.
C# 
// C# program to count number of subarrays // whose maximum element is greater than K. using System; class GFG {  // Return number of subarrays whose maximum  // element is less than or equal to K.  static int countSubarray(int[] arr int n int k)  {  // To store count of subarrays with all  // elements less than or equal to k.  int s = 0;  // Traversing the array.  int i = 0;  while (i < n) {  // If element is greater than k ignore.  if (arr[i] > k) {  i++;  continue;  }  // Counting the subarray length whose  // each element is less than equal to k.  int count = 0;  while (i < n && arr[i] <= k) {  i++;  count++;  }  // Summing number of subarray whose  // maximum element is less than equal to k.  s += ((count * (count + 1)) / 2);  }  return (n * (n + 1) / 2 - s);  }  // Driver code  public static void Main()  {  int[] arr = {1 2 3};  int k = 2;  int n = arr.Length;  Console.WriteLine(countSubarray(arr n k));  } } // This code is contributed by vt_m.
JavaScript 
<script>  // Javascript program to count number of subarrays  // whose maximum element is greater than K.    // Return number of subarrays whose maximum  // element is less than or equal to K.  function countSubarray(arr n k)  {  // To store count of subarrays with all  // elements less than or equal to k.  let s = 0;    // Traversing the array.  let i = 0;  while (i < n) {    // If element is greater than k ignore.  if (arr[i] > k) {  i++;  continue;  }    // Counting the subarray length whose  // each element is less than equal to k.  let count = 0;  while (i < n && arr[i] <= k) {  i++;  count++;  }    // Summing number of subarray whose  // maximum element is less than equal to k.  s += parseInt((count * (count + 1)) / 2 10);  }    return (n * parseInt((n + 1) / 2 10) - s);  }    let arr = [1 2 3];  let k = 2;  let n = arr.length;  document.write(countSubarray(arr n k));   </script>
PHP 
 // PHP program to count number of subarrays // whose maximum element is greater than K. // Return number of subarrays whose maximum // element is less than or equal to K. function countSubarray( $arr $n $k) { // To store count of subarrays with all // elements less than or equal to k. $s = 0; // Traversing the array. $i = 0; while ($i < $n) { // If element is greater than k // ignore. if ($arr[$i] > $k) { $i++; continue; } // Counting the subarray length  // whose each element is less // than equal to k. $count = 0; while ($i < $n and $arr[$i] <= $k) { $i++; $count++; } // Summing number of subarray whose // maximum element is less than // equal to k. $s += (($count * ($count + 1)) / 2); } return ($n * ($n + 1) / 2 - $s); } // Driven Program $arr = array( 1 2 3 ); $k = 2; $n = count($arr); echo countSubarray($arr $n $k); // This code is contributed by anuj_67. ?>

산출 
3

시간 복잡도: O(n).
보조 공간: O(1)

접근 방식 2: 최대 요소 > K를 갖는 하위 배열 계산

이 접근 방식에서는 K보다 큰 인덱스 i에 요소를 포함하여 구성할 수 있는 하위 배열의 수를 간단히 찾습니다. 도착 [ 나는 ] > K 그러면 이 요소가 존재하는 모든 하위 배열은 k보다 큰 값을 갖게 되므로 K보다 큰 모든 요소에 대해 이러한 하위 배열을 모두 계산하여 답에 추가하면 됩니다. 먼저 두 개의 변수를 초기화합니다. 년 = 0 여기에는 답변이 포함되어 있으며 이전 = -1 이는 K보다 큰 이전 요소의 인덱스를 추적합니다.

이를 위해서는 모든 arr [ i ] > K 에 세 ​​개의 값만 있으면 됩니다.

  1. 인덱스에서 시작하는 하위 배열 수 나 . 이것은 (N-i) . 참고: 여기에는 이 요소 자체인 단일 요소를 포함하는 하위 배열이 포함되었습니다. { 도착 [ 나는 ] }
  2. 이 인덱스에서 끝나는 하위 배열 수 나 하지만 이 하위 배열의 시작 인덱스는 인덱스 뒤에 있습니다. 이전 K보다 큰 이전 요소의 경우 왜 이렇게 합니까? 해당 요소에 대해서는 이미 답을 계산했어야 하므로 동일한 하위 배열을 두 번 이상 계산하고 싶지 않습니다. 따라서 이 값은 다음과 같을 것입니다. ( 나 - 이전 - 1 ) . 참고: 여기서는 자체적으로 단일 요소인 하위 배열 { arr [ i ] } 를 이미 계산했기 때문에 1을 뺍니다. 위의 참고 사항을 참조하세요. 
  3. 다음보다 작은 시작 인덱스를 갖는 하위 배열의 수 나 그러나 보다 큼 이전 종료 인덱스가 다음보다 큼 나 . 따라서 arr[i]가 사이에 있는 모든 하위 배열입니다. 이는 위의 두 값을 곱하여 계산할 수 있습니다. 그것들을 다음과 같이 말하자 엘 = ( N - 나는 - 1 ) 그리고 R = ( i - 이전 -1 ). 이제 우리는 이 L과 R을 곱하기만 하면 됩니다. 왜냐하면 i의 왼쪽에 있는 모든 1개의 인덱스에 대해 서로 다른 하위 배열을 기본 수학으로 만들 수 있는 R 인덱스가 있기 때문입니다. 그래서 이것은 된다 L * R . 여기서 L의 값에서 실제로 1을 뺀 것에 주목하세요. 이렇게 하지 않으면 L*R에 인덱스 i를 포함합니다. 이는 1번 유형 하위 배열을 다시 포함했음을 의미합니다. 포인트 1을 참조하세요.    

다음은 이 접근 방식의 구현입니다.

C++ 
// C++ program to count number of subarrays // whose maximum element is greater than K. #include    using namespace std; long long countSubarray(int arr[] int n int k) {  long long ans = 0 ;  int prev = - 1; //prev for keeping track of index of previous element > k;  for(int i = 0 ; i < n ; i++ ) {  if ( arr [ i ] > k ) {  ans += n - i ; //subarrays starting at index i.  ans += i - prev - 1 ; //subarrays ending at index i but starting after prev.  ans += ( n - i - 1 ) * 1LL * ( i - prev - 1 ) ; //subarrays having index i element in between.  prev = i; // updating prev  }  }  return ans; } // Driven Program int main() {  int arr[] = { 4 5 1 2 3 };  int k = 2;  int n = sizeof(arr) / sizeof(arr[0]);  cout << countSubarray(arr n k);  return 0; } // This Code is contributed by Manjeet Singh.
Java 
// Java program to count number of subarrays // whose maximum element is greater than K. import java.util.*; public class GFG {  static long countSubarray(int arr[] int n int k)  {  long ans = 0 ;  int prev = - 1; //prev for keeping track of index of previous element > k;  for(int i = 0 ; i < n ; i++ ) {  if ( arr [ i ] > k ) {  ans += n - i ; //subarrays starting at index i.  ans += i - prev - 1 ; //subarrays ending at index i but starting after prev.  ans += ( n - i - 1 ) * 1L * ( i - prev - 1 ) ; //subarrays having index i element in between.  prev = i; // updating prev  }  }  return ans;  }  // Driver code  public static void main(String[] args)  {  int arr[] = { 4 5 1 2 3 };  int k = 2;  int n = arr.length;  System.out.print(countSubarray(arr n k));  } } //This Code is contributed by Manjeet Singh
Python3 
# Python program to count number of subarrays # whose maximum element is greater than K. def countSubarray( arr n k): ans = 0 ; prev = - 1; #prev for keeping track of index of previous element > k; for i in range(0n): if ( arr [ i ] > k ) : ans += n - i ; #subarrays starting at index i. ans += i - prev - 1 ; #subarrays ending at index i but starting after prev. ans += ( n - i - 1 ) * ( i - prev - 1 ) ; #subarrays having index i element in between. prev = i; # updating prev return ans; # Driven Program arr = [ 4 5 1 2 3 ]; k = 2; n = len(arr); print(countSubarray(arr n k)); # this code is contributed by poojaagarwal2.
C# 
// C# program to count number of subarrays // whose maximum element is greater than K. using System; public class GFG {  static long countSubarray(int[] arr int n int k)  {  long ans = 0;  int prev = -1; // prev for keeping track of index of  // previous element > k;  for (int i = 0; i < n; i++) {  if (arr[i] > k) {  ans += n - i; // subarrays starting at index  // i.  ans += i - prev  - 1; // subarrays ending at index i  // but starting after prev.  ans += (n - i - 1) * (long)1  * (i - prev  - 1); // subarrays having index i  // element in between.  prev = i; // updating prev  }  }  return ans;  }  // Driver code  public static void Main(string[] args)  {  int[] arr = { 4 5 1 2 3 };  int k = 2;  int n = arr.Length;  Console.Write(countSubarray(arr n k));  } } // This Code is contributed by Karandeep1234
JavaScript 
// Javascript program to count number of subarrays // whose maximum element is greater than K. function countSubarray(arr n k) {  let ans = 0 ;  //prev for keeping track of index of previous element > k;  let prev = - 1;   for(let i = 0 ; i < n ; i++ ) {  if ( arr [ i ] > k ) {  //subarrays starting at index i.  ans += n - i ;   //subarrays ending at index i but starting after prev.  ans += i - prev - 1 ;  //subarrays having index i element in between.  ans += ( n - i - 1 ) * 1 * ( i - prev - 1 ) ;   // updating prev  prev = i;   }  }  return ans; } // Driven Program  let arr = [ 4 5 1 2 3 ];  let k = 2;  let n = arr.length;  document.write(countSubarray(arr n k));

산출 
12

시간 복잡도: O(n).

접근법 3: 슬라이딩 윈도우 기법.

연산:

1. 변수 초기화 년 = 0 변수 최대요소 = 0 그리고 변수 개수 = 0 .

2. 각 요소에 대해 다음을 수행하여 배열을 반복합니다.

  에이. 현재 요소 즉, 도착[ 나는 ] 현재 최대 업데이트 최대값보다 큽니다. 즉, 라디오 = arr ] 그리고 카운트를 0으로 재설정합니다.

  비. 현재 요소가 현재 최대값보다 작거나 같으면 개수를 늘립니다.

  기음. 만약에 최대요소 그러면 k보다 크다 개수 추가 하위 배열을 최종 답변으로 업데이트하고 최대 요소 현재 요소에.

3. 최종 답변을 반환합니다.

다음은 슬라이딩 윈도우 기술의 구현입니다.

C++ 
#include    using namespace std; int countSubarray(int arr[] int n int k) {  int maxElement = 0 count = 0 ans = 0;  for(int i=0; i<n; i++) {  if(arr[i] > maxElement) {  maxElement = arr[i];  count = 0;  }  else {  count++;  }  if(maxElement > k) {  ans += (i - count + 1);  maxElement = arr[i];  count = 0;  }  }  return ans; } int main() {  int arr[] = {1 2 3 4};  int k = 1;  int n = sizeof(arr) / sizeof(arr[0]);  cout << countSubarray(arr n k);  return 0; } // This code is contributed by Vaibhav Saroj
C 
#include  int countSubarray(int arr[] int n int k) {  int maxElement = 0 count = 0 ans = 0;  for(int i=0; i<n; i++) {  if(arr[i] > maxElement) {  maxElement = arr[i];  count = 0;  }  else {  count++;  }  if(maxElement > k) {  ans += (i - count + 1);  maxElement = arr[i];  count = 0;  }  }  ans += (count * (count + 1)) / 2;  return ans; } int main() {  int arr[] = {1 2 3 4};  int k = 1;  int n = sizeof(arr) / sizeof(arr[0]);  printf('%dn' countSubarray(arr n k));  return 0; } // This code is contributed by Vaibhav Saroj
Java 
import java.util.*; public class GFG {  // Function to count the number of subarrays with the maximum element greater than k  public static int countSubarray(int[] arr int n int k) {  int maxElement = 0; // Variable to store the maximum element encountered so far  int count = 0; // Variable to count the length of the subarray with elements <= k  int ans = 0; // Variable to store the final result  for (int i = 0; i < n; i++) {  if (arr[i] > maxElement) {  // If the current element is greater than the maximum element  // update the maximum element and reset the count to zero.  maxElement = arr[i];  count = 0;  } else {  // increment the count  count++;  }  if (maxElement > k) {  // If the maximum element in the current subarray is greater than k  // add the count of subarrays ending at the current index (i - count + 1) to the result.  ans += (i - count + 1);  // Reset the maximum element and count to zero.  maxElement = arr[i];  count = 0;  }  }  // Return the final result  return ans;  }  public static void main(String[] args) {  int[] arr = {1 2 3 4};  int k = 1;  int n = arr.length;  // Call the countSubarray function to count the number of subarrays with maximum element greater than k  int result = countSubarray(arr n k);  System.out.println(result);  } } // THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL
Python3 
def countSubarray(arr n k): maxElement count ans = 0 0 0 for i in range(n): if arr[i] > maxElement: maxElement = arr[i] count = 0 else: count += 1 if maxElement > k: ans += (i - count + 1) maxElement = arr[i] count = 0 ans += (count * (count + 1)) // 2 return ans arr = [1 2 3 4] k = 1 n = len(arr) print(countSubarray(arr n k)) # This code is contributed by Vaibhav Saroj
C# 
using System; public class Program {  public static int CountSubarray(int[] arr int n int k) {  int maxElement = 0 count = 0 ans = 0;  for(int i=0; i<n; i++) {  if(arr[i] > maxElement) {  maxElement = arr[i];  count = 0;  }  else {  count++;  }  if(maxElement > k) {  ans += (i - count + 1);  maxElement = arr[i];  count = 0;  }  }  ans += (count * (count + 1)) / 2;  return ans;  }  public static void Main() {  int[] arr = {1 2 3 4};  int k = 1;  int n = arr.Length;  Console.WriteLine(CountSubarray(arr n k));  } } // This code is contributed by Vaibhav Saroj
JavaScript 
function countSubarray(arr n k) {  let maxElement = 0 count = 0 ans = 0;  for(let i=0; i<n; i++) {  if(arr[i] > maxElement) {  maxElement = arr[i];  count = 0;  }  else {  count++;  }  if(maxElement > k) {  ans += (i - count + 1);  maxElement = arr[i];  count = 0;  }  }  ans += (count * (count + 1)) / 2;  return ans; } let arr = [1 2 3 4]; let k = 1; let n = arr.length; console.log(countSubarray(arr n k)); // This code is contributed by Vaibhav Saroj

산출 
9

슬라이딩 윈도우 기술은 다음에 의해 기여되었습니다. 바이바브 사로즈 .

시간 복잡도: O(n).
공간 복잡도: O( 1 ).

여기서 연습하세요 하위 배열 수 .

퀴즈 만들기