NGE sayında doğru problemə bir verdik array massivin indeksini əks etdirən sorğu sayı n və q ölçülü bir []. Hər bir sorğu üçün ümumi sayını çap edirəm növbəti böyük elementlər bu doğru.
Mündəricat
misal
Input
a [] = {3, 4, 2, 7, 5, 8, 10, 6}
q1 = 0
q2 = 5
Buraxılış
4
1
Input
a [] = {1, 2, 3, 4, 5, 6, 7}
q1 = 0
Buraxılış
6
Sadəlövh metod
Alqoritm
- N ölçülü bir [] massivi başladın.
- NGE-ləri saymaq və 0 olaraq başlamaq üçün c dəyişənini yaradın.
- LastEle dəyişənini yaradın və massivin dəyərini q indeksində, yəni sorğuda saxlayın.
- Q + 1-dən n-1-ə keçin və cari indeksdə [] massivinin dəyərinin lastEle-dən çox olub olmadığını yoxlayın, cari indeksdəki a [] massivinin dəyəri kimi lastEle-i yeniləyin. Sayını artırın.
- Sayını çap edin.
Sağdakı NGE sayını saymaq üçün C ++ proqramı
#include <bits/stdc++.h>
using namespace std;
void count(int a[], int n, int q){
int c = 0;
int lastEle = a[q];
for(int i=q+1; i<n; i++){
if(a[i]>lastEle){
lastEle = a[i];
c++;
}
}
cout<<c<<endl;
}
int main(){
int a[] = {3, 4, 2, 7, 5, 8, 10, 6};
int n = sizeof(a) / sizeof(a[0]);
count(a, n, 0);
count(a, n, 5);
return 0;
}
4 1
Sağdakı NGE sayını saymaq üçün Java Proqramı
import java.util.*;
class NGE{
static void count(int a[], int n, int q){
int c = 0;
int lastEle = a[q];
for(int i=q+1; i<n; i++){
if(a[i]>lastEle){
lastEle = a[i];
c++;
}
}
System.out.println(c);
}
public static void main(String args[]){
int a[] = {3, 4, 2, 7, 5, 8, 10, 6};
int n = a.length;
count(a, n, 0);
count(a, n, 5);
}
}
4 1
Mürəkkəblik təhlili
Zamanın mürəkkəbliyi: O (n), burada n a [] massivinin ölçüsüdür.
Köməkçi məkan: O (1), çünki daimi əlavə yer istifadə etdik.
Səmərəli metod
Alqoritm
- N ölçülü bir ədəd [eyni] ölçülü bir dp massivi başladın.
- N ölçüsü yanında [] bir sıra yaradın və elementini 0 olaraq təyin edin.
- Bir yığın yaradın və içərisinə 0 basın.
- 1-dən n-1-ə keçin və yığın boş deyilsə, yığının yuxarı hissəsinə bərabər olan indeksdəki bir [] massivindəki dəyərin indiki indeksdəki [] massivindəki dəyərdən az olub olmadığını yoxlayın. indiki indeks olaraq yığının üstünə bərabər olan indeksin yanında bir sıra. Yığın üst hissəsini açın.
- Başqa bir dövrəni pozun.
- Hazırkı indeksi yığında itələyin.
- Yığın boş deyilsə, dizinin yanındakı dizinin üstündəki indeksin yanında -1 olaraq yeniləyin. Yığın üst hissəsini açın.
- N-2-dən 0-a qədər keçin və cari indeksdə növbəti sıradakı yoxlama dəyəri -1-dir, indiki indeksdəki dp-dəki dəyəri 0-a kimi yeniləyin. Cari indeksdəki sonrakı massivdəki başqa yeniləmə dəyəri 1 + dp [next [i] ].
- Hər bir sorğu üçün dp [I] yazdırmaq bərabərdir.
Sağdakı NGE sayını saymaq üçün C ++ proqramı
#include <bits/stdc++.h>
using namespace std;
void computeNext(int next[], int a[], int n){
stack<int> s;
s.push(0);
for(int i = 1; i < n; i++){
while(!s.empty()){
int cur = s.top();
if(a[cur] < a[i]){
next[cur] = i;
s.pop();
}
else{
break;
}
}
s.push(i);
}
while(!s.empty()){
int cur = s.top();
next[cur] = -1;
s.pop();
}
}
void count(int a[], int dp[], int n){
int next[n];
memset(next, 0, sizeof(next));
computeNext(next, a, n);
for(int i = n-2; i >= 0; i--){
if(next[i] == -1){
dp[i] = 0;
}
else{
dp[i] = 1 + dp[next[i]];
}
}
}
int answerQuery(int dp[], int index){
return dp[index];
}
int main(){
int a[] = {3, 4, 2, 7, 5, 8, 10, 6};
int n = sizeof(a) / sizeof(a[0]);
int dp[n];
count(a, dp, n);
cout<<answerQuery(dp, 0)<<endl;
cout<<answerQuery(dp, 5)<<endl;
return 0;
}
4 1
Sağdakı NGE sayını saymaq üçün Java Proqramı
import java.util.*;
class NGE{
static void computeNext(int next[], int a[], int n){
Stack<Integer> s = new Stack<Integer>();
s.push(0);
for(int i = 1; i < n; i++){
while(s.size() > 0){
int cur = s.peek();
if(a[cur] < a[i]){
next[cur] = i;
s.pop();
}
else{
break;
}
}
s.push(i);
}
while(s.size() > 0){
int cur = s.peek();
next[cur] = -1;
s.pop();
}
}
static void count(int a[], int dp[], int n){
int next[] = new int[n];
for(int i = 0; i < n; i++){
next[i] = 0;
}
computeNext(next, a, n);
for(int i = n-2; i >= 0; i--){
if(next[i] == -1){
dp[i] = 0;
}
else{
dp[i] = 1 + dp[next[i]];
}
}
}
static int answerQuery(int dp[], int index){
return dp[index];
}
public static void main(String args[]){
int a[] = {3, 4, 2, 7, 5, 8, 10, 6};
int n = a.length;
int dp[] = new int[n];
count(a, dp, n);
System.out.println(answerQuery(dp, 0));
System.out.println(answerQuery(dp, 5));
}
}
4 1
Mürəkkəblik təhlili
Zamanın mürəkkəbliyi: O (1), çünki bütün sorğular əvvəlcədən hesablamalara görə daimi vaxt tələb edir.
Köməkçi məkan: O (n), burada n a [] massivinin ölçüsüdür.
