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
모든 창 크기에 대해 최소값을 찾는 순진한 방법
암호알고리즘
- n 크기의 배열 a []를 초기화합니다.
- 배열 a []를 통과합니다. 정수 변수를 초기화하여 최소값의 최대 값을 저장하고 해당 값을 INT_MIN으로 설정합니다.
- 그 후, 외부 루프의 현재 인덱스와 동일한 크기 배열의 모든 창을 반복합니다. 현재 창의 최소값을 저장하는 변수를 초기화하고 그 안에 배열 a []의 현재 인덱스에 값을 저장합니다.
- 마찬가지로 Traverse는 배열의 현재 창의 최소 요소를 찾고 변수에 최소값을 저장하여 현재 창의 최소값을 저장합니다.
- 현재 창의 최소값이 최소값의 최대 값보다 큰지 확인하고 최소값의 최대 값을 현재 창의 최소값의 변수로 업데이트합니다.
- 최소값의 최대 값을 출력합니다.
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) 우리는 일정한 추가 공간을 사용했기 때문입니다.
모든 창 크기에 대한 최소값을 찾는 효율적인 방법
암호알고리즘
- n 크기의 배열 a []를 초기화합니다.
- 만들기 스택 데이터 구조와 길이 n + 2의 좌우 1 개의 배열. 왼쪽 배열의 모든 값을 -1로, 오른쪽 배열을 n으로 설정합니다.
- 0에서 n-1로 이동하고 스택이 비어 있지 않고 인덱스에있는 배열 a []의 값이 스택의 맨 위와 같고 현재 인덱스의 배열 a []에있는 값보다 크거나 같으면 스택 맨 위에있는 요소.
- 스택이 비어 있지 않은 경우 스택의 맨 위에있는 배열의 현재 인덱스에서 값을 업데이트합니다. 스택의 현재 인덱스를 푸시합니다.
- 스택이 비어 있지 않은 동안 스택 맨 위에있는 요소를 팝합니다.
- 마찬가지로, n-1에서 0으로 순회하고 스택이 비어 있지 않고 인덱스에있는 배열 a []의 값이 스택의 맨 위와 같으면 현재 인덱스에있는 배열 a []의 값보다 크거나 같습니다. 스택 맨 위에있는 요소를 팝합니다.
- 스택이 비어 있지 않은 경우 스택의 맨 위에있는 배열의 현재 인덱스에서 값을 업데이트합니다. 스택의 현재 인덱스를 푸시합니다.
- 응답을 저장하고 모든 값을 1으로 설정하기 위해 크기 n + 0의 또 다른 배열을 만듭니다.
- 0에서 n-1까지 순회하여 오른쪽과 왼쪽 배열의 현재 색인에있는 값 사이의 창 길이를 찾고 배열 a []의 현재 색인에서 값의 최대 값으로 응답 배열을 업데이트하고 색인이 같음 답변 배열의 계산 된 간격으로.
- 답변 배열을 인쇄하십시오.
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 요소에 스택 공간을 사용했기 때문입니다.
