주어진 배열의 모든 창 크기에 대한 최소값 찾기


난이도 중급
자주 묻는 질문 아마존 Directi Flipkart SAP 연구소 조호 (Zoho)
배열 슬라이딩 윈도우 스택

n 크기의 배열 a []가 주어집니다. 1에서 n까지 다양한 모든 창 크기 정렬 주어진 배열의 모든 창 크기에 대해 최소값을 인쇄하거나 찾습니다.

주어진 배열의 모든 창 크기에 대한 최소값 찾기

입력 : a [] = {10, 20, 30, 50, 10, 70, 30}

출력 : 70 30 20 10 10 10 10

입력 : a [] = {10, 20, 30}

출력 : +30 20 10 XNUMX

모든 창 크기에 대해 최소값을 찾는 순진한 방법

암호알고리즘

  1. n 크기의 배열 a []를 초기화합니다.
  2. 배열 a []를 통과합니다. 정수 변수를 초기화하여 최소값의 최대 값을 저장하고 해당 값을 INT_MIN으로 설정합니다.
  3. 그 후, 외부 루프의 현재 인덱스와 동일한 크기 배열의 모든 창을 반복합니다. 현재 창의 최소값을 저장하는 변수를 초기화하고 그 안에 배열 a []의 현재 인덱스에 값을 저장합니다.
  4. 마찬가지로 Traverse는 배열의 현재 창의 최소 요소를 찾고 변수에 최소값을 저장하여 현재 창의 최소값을 저장합니다.
  5. 현재 창의 최소값이 최소값의 최대 값보다 큰지 확인하고 최소값의 최대 값을 현재 창의 최소값의 변수로 업데이트합니다.
  6. 최소값의 최대 값을 출력합니다.

C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
void printMaxOfMin(int a[], int n){ 
    
    for(int k=1; k<=n; k++){ 
        int maxOfMin = INT_MIN; 
  
        for(int i = 0; i <= n-k; i++){ 
            int min = a[i]; 
            for(int j = 1; j < k; j++){ 
                if(a[i+j] < min){ 
                    min = a[i+j]; 
                }
            } 
  
            if(min > maxOfMin){ 
              maxOfMin = min; 
            }
        } 
  
        cout << maxOfMin << " "; 
    } 
} 
  
int main(){ 
    int a[] = {10, 20, 30, 50, 10, 70, 30}; 
    int n = sizeof(a)/sizeof(a[0]); 
    
    printMaxOfMin(a, n); 
    
    return 0; 
}
70 30 20 10 10 10 10

자바 프로그램

class MaxOfMin{
    
    static int a[] = {10, 20, 30, 50, 10, 70, 30}; 
      
    static void printMaxOfMin(int n){ 
        
        for(int k=1; k<=n; k++){ 
            int maxOfMin = Integer.MIN_VALUE; 
       
            for(int i = 0; i <= n-k; i++){ 
                int min = a[i]; 
                
                for(int j = 1; j < k; j++){ 
                    if(a[i+j] < min){ 
                        min = a[i+j];
                    }
                } 
       
                if(min > maxOfMin){ 
                    maxOfMin = min; 
                }
            } 
       
            System.out.print(maxOfMin + " "); 
        } 
    } 
      
    public static void main(String[] args){ 
        printMaxOfMin(a.length); 
    } 
}
70 30 20 10 10 10 10

모든 창 크기에 대한 최소값 찾기를위한 복잡성 분석

시간 복잡성 : 의 위에3) 여기서 n은 주어진 배열 a []의 요소 수입니다.

보조 공간 : O (1) 우리는 일정한 추가 공간을 사용했기 때문입니다.

모든 창 크기에 대한 최소값을 찾는 효율적인 방법

암호알고리즘

  1. n 크기의 배열 a []를 초기화합니다.
  2. 만들기 스택 데이터 구조와 길이 n + 2의 좌우 1 개의 배열. 왼쪽 배열의 모든 값을 -1로, 오른쪽 배열을 n으로 설정합니다.
  3. 0에서 n-1로 이동하고 스택이 비어 있지 않고 인덱스에있는 배열 a []의 값이 스택의 맨 위와 같고 현재 인덱스의 배열 a []에있는 값보다 크거나 같으면 스택 맨 위에있는 요소.
  4. 스택이 비어 있지 않은 경우 스택의 맨 위에있는 배열의 현재 인덱스에서 값을 업데이트합니다. 스택의 현재 인덱스를 푸시합니다.
  5. 스택이 비어 있지 않은 동안 스택 맨 위에있는 요소를 팝합니다.
  6. 마찬가지로, n-1에서 0으로 순회하고 스택이 비어 있지 않고 인덱스에있는 배열 a []의 값이 스택의 맨 위와 같으면 현재 인덱스에있는 배열 a []의 값보다 크거나 같습니다. 스택 맨 위에있는 요소를 팝합니다.
  7. 스택이 비어 있지 않은 경우 스택의 맨 위에있는 배열의 현재 인덱스에서 값을 업데이트합니다. 스택의 현재 인덱스를 푸시합니다.
  8. 응답을 저장하고 모든 값을 1으로 설정하기 위해 크기 n + 0의 또 다른 배열을 만듭니다.
  9. 0에서 n-1까지 순회하여 오른쪽과 왼쪽 배열의 현재 색인에있는 값 사이의 창 길이를 찾고 배열 a []의 현재 색인에서 값의 최대 값으로 응답 배열을 업데이트하고 색인이 같음 답변 배열의 계산 된 간격으로.
  10. 답변 배열을 인쇄하십시오.

C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
void printMaxOfMin(int a[], int n){ 
    
    stack<int> s;  
  
    int left[n+1];   
    int right[n+1];  
  
    for(int i=0; i<n; i++){ 
        left[i] = -1; 
        right[i] = n; 
    } 
  
    for(int i=0; i<n; i++){ 
        while(!s.empty() && a[s.top()] >= a[i]){ 
            s.pop(); 
        }
  
        if(!s.empty()){ 
            left[i] = s.top();
        }
  
        s.push(i); 
    } 
  
    while(!s.empty()){ 
        s.pop(); 
    }
  
    for(int i = n-1 ; i>=0 ; i--){ 
        while(!s.empty() && a[s.top()] >= a[i]){ 
            s.pop(); 
        }
  
        if(!s.empty()){ 
            right[i] = s.top(); 
        }
  
        s.push(i); 
    } 
  
    int ans[n+1]; 
    for(int i=0; i<=n; i++){ 
        ans[i] = 0; 
    }
  
    for(int i=0; i<n; i++){ 
        int len = right[i] - left[i] - 1; 
  
        ans[len] = max(ans[len], a[i]); 
    } 
  
    for(int i=n-1; i>=1; i--){ 
        ans[i] = max(ans[i], ans[i+1]);
    }
  
    for(int i=1; i<=n; i++){ 
        cout << ans[i] << " ";
    }
} 
  
int main(){ 
    int a[] = {10, 20, 30, 50, 10, 70, 30}; 
    int n = sizeof(a)/sizeof(a[0]); 
    
    printMaxOfMin(a, n); 
    
    return 0; 
}
70 30 20 10 10 10 10

자바 프로그램

import java.util.Stack;

class MaxOfMin{
    
    static int a[] = {10, 20, 30, 50, 10, 70, 30}; 
      
    static void printMaxOfMin(int n){ 
        
        Stack<Integer> s = new Stack<>(); 
       
        int left[] = new int[n+1];   
        int right[]  = new int[n+1];  
       
        for(int i=0; i<n; i++){ 
            left[i] = -1; 
            right[i] = n; 
        } 
       
        for(int i=0; i<n; i++){ 
            while(!s.empty() && a[s.peek()] >= a[i]){ 
                s.pop(); 
            }
       
            if(!s.empty()){ 
                left[i] = s.peek();
            }
       
            s.push(i); 
        } 
       
        while(!s.empty()){ 
            s.pop(); 
        }
       
        for(int i = n-1 ; i>=0 ; i--){ 
            while(!s.empty() && a[s.peek()] >= a[i]){ 
                s.pop(); 
            }
       
            if(!s.empty()){ 
                right[i] = s.peek(); 
            }
       
            s.push(i); 
        } 
       
        int ans[] = new int[n+1]; 
        for(int i=0; i<=n; i++){ 
            ans[i] = 0; 
        }
       
        for(int i=0; i<n; i++){ 
            int len = right[i] - left[i] - 1; 
            ans[len] = Math.max(ans[len], a[i]); 
        } 
       
        for(int i=n-1; i>=1; i--){ 
            ans[i] = Math.max(ans[i], ans[i+1]);
        }
       
        for(int i=1; i<=n; i++){ 
            System.out.print(ans[i] + " "); 
        }
    } 
      
    public static void main(String[] args){ 
        printMaxOfMin(a.length); 
    } 
}
70 30 20 10 10 10 10

모든 창 크기에 대한 최소값 찾기를위한 복잡성 분석

시간 복잡성 : O (n) 여기서 n은 주어진 배열 a []의 요소 수입니다.

보조 공간 : O (n) n 요소에 스택 공간을 사용했기 때문입니다.

참조