Берілген массивтегі әр терезе өлшемі үшін ең кіші мәнді табыңыз


Күрделілік дәрежесі орта
Жиі кіреді Amazon Directi Flipkart SAP зертханалары Зохо
Array Сырғымалы терезе үйме

N өлшемді массив берілген []. 1-ден n-ге дейін өзгеретін әр терезе өлшемі үшін массив берілген массивтегі терезенің әрбір өлшемі үшін минимумды басып шығарыңыз немесе табыңыз.

Берілген массивтегі әр терезе өлшемі үшін ең кіші мәнді табыңыз

мысал

Кіріс: a [] = {10, 20, 30, 50, 10, 70, 30}

Шығару: 70 30 20 10 10 10 10

Кіріс: a [] = {10, 20, 30}

Шығару: 30 20 10

Терезенің кез-келген өлшемі үшін максимумды табудың қарапайым әдісі

Алгоритм

  1. N өлшемді [] массивін инициализациялаңыз.
  2. A [] массиві арқылы өтіңіз. Ең төменгі минимумды сақтау үшін бүтін айнымалы мәнді бастаңыз және оның мәнін INT_MIN деп орнатыңыз.
  3. Осыдан кейін, өлшемдердің жиымының барлық терезелерін сыртқы циклдің ағымдағы индексіне теңестіріңіз. Ағымдағы терезенің минимумын сақтау үшін айнымалыны инициализациялаңыз және ондағы [] массивінде ағымдағы индекстегі мәнді сақтаңыз.
  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

Java бағдарламасы

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

Әр терезенің өлшемі үшін минимумды табу үшін күрделіліктің талдауы

Уақыттың күрделілігі: O (n3) мұндағы n - берілген а массивіндегі элементтер саны [].

Көмекші кеңістік: O (1), өйткені біз тұрақты қосымша кеңістікті пайдаландық.

Терезенің кез-келген өлшемі үшін максимумды табудың тиімді әдісі

Алгоритм

  1. N өлшемді [] массивін инициализациялаңыз.
  2. а жасау Стек мәліметтер құрылымы және n + 2 ұзындығынан солға және оңға 1 массив. Массивтің сол жақтағы мәндерін -1-ге, ал жиымның n-ге оң мәндерін қойыңыз.
  3. 0-ден n-1-ге дейін жүріңіз және стек бос емес, ал индекс бойынша [] массивінің мәні стектің жоғарғы жағына тең болса, [[массивтің) мәнінен ағымдағы индекстегі мәннен үлкен немесе тең болады, стектің жоғарғы жағындағы элемент.
  4. Егер стек бос болмаса, стектің жоғарғы бөлігі ретінде қалдырылған жиымдағы ағымдағы индекстегі мәнді жаңартыңыз. Ағымдағы индексті стекке итеріңіз.
  5. Стек бос болмаса да, элементті стектің жоғарғы жағына қойыңыз.
  6. Сол сияқты n-1-ден 0-ге дейін жүріңіз, ал стек бос емес, ал индекс бойынша а [] жиымының мәні стектің жоғарғы жағына тең болса, ағымдағы индекстегі а [] жиымындағы мәннен үлкен немесе тең болады, элементті стектің жоғарғы жағына қойыңыз.
  7. Егер стек бос болмаса, жиымның ағымдағы индексіндегі мәнді стектің жоғарғы жағы ретінде жаңартыңыз. Ағымдағы индексті стекке итеріңіз.
  8. Жауаптарды сақтау үшін n + 1 өлшемді басқа массив құрыңыз және оның барлық мәндерін 0 деп қойыңыз.
  9. 0-ден n-1-ге дейін жүріп өтіп, оң және сол жиымның ағымдағы индексіндегі мәндер арасындағы терезенің ұзындығын табыңыз және жауаптар массивін максимум ретінде а [] жиымының ағымдағы индексінде және тең индексте жаңартыңыз жауаптар массивінің есептелген интервалына дейін.
  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

Java бағдарламасы

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 - берілген [] массивіндегі элементтер саны.

Көмекші кеңістік: O (n), өйткені біз n элемент үшін стек кеңістігін қолдандық.

Әдебиеттер тізімі