在圆形数组中找到下一个更大的元素|集合 2
给定一个由 N 个整数组成的圆形数组 arr[] ，任务是为圆形数组的每个元素打印下一个更大的元素。不存在更大元素的元素，打印-1”。
示例:
输入: arr[] = {5，6，7} 输出: 6 7 -1 解释:每个数组元素的下一个较大元素如下: 对于 arr[0] (= 5) - > 6 对于 arr[1] (= 6) - > 7 对于 arr[2] (= 7)，数组中不存在较大的元素。因此，打印-1。
输入: arr[] = {4，-2，5，3} 输出: 5 5 -1 4 解释:每个数组元素的下一个较大元素如下: For arr0->5 For arr1->5 For arr2，数组中不存在较大元素。因此，打印-1。 为 arr[3] (= 3) - > 4
天真方法:解决这个问题最简单的方法在本文之前的帖子中讨论过。
时间复杂度:O(N2) 辅助空间: O(N)
替代方法:参考本文的前一篇文章来获得空间优化的朴素方法。
时间复杂度:O(N2) 辅助空间: O(1)
高效方法:为了优化上述方法，想法是使用下一个更大元素的概念，该元素使用堆栈数据结构。按照以下步骤解决问题:
- 初始化一个堆栈来存储数组的索引，以及一个大小为 N 的数组nge【】，该数组存储每个数组元素的下一个较大元素。
- 遍历数组，对于每个索引，执行以下操作:
- 如果堆栈非空且当前 i th 数组元素大于堆栈的顶部元素，则弹出堆栈的顶部元素并通过在其中存储 arr[i % N] 来更新nge【ST . top()】。重复此操作，直到堆栈为空或当前元素小于堆栈顶部的元素。
- 如果堆栈为空或当前元素小于堆栈顶部，将 (i % N) 推入堆栈。
- 在 N 元素的单次遍历之后，堆栈包含在(N–1)第个索引之前没有下一个更大元素的元素。由于数组是圆形，再次考虑 0 第个索引中的所有元素，找到剩余元素的下一个更大的元素。
- 由于数组遍历 2 次，所以最好使用 i % N 而不是 i 。
- 完成以上步骤后，打印数组 nge[] 。
下面是上述方法的实现:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the NGE for the
// given circular array arr[]
void printNGE(int* arr, int n)
{
// Initialize stack and nge[] array
stack<int> s;
int nge[n], i = 0;
// Initialize nge[] array to -1
for (i = 0; i < n; i++) {
nge[i] = -1;
}
i = 0;
// Traverse the array
while (i < 2 * n) {
// If stack is not empty and
// current element is greater
// than top element of the stack
while (!s.empty()
&& arr[i % n] > arr[s.top()]) {
// Assign next greater element
// for the top element of the stack
nge[s.top()] = arr[i % n];
// Pop the top element
// of the stack
s.pop();
}
s.push(i % n);
i++;
}
// Print the nge[] array
for (i = 0; i < n; i++) {
cout << nge[i] << " ";
}
}
// Driver Code
int main()
{
int arr[] = { 4, -2, 5, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
printNGE(arr, N);
return 0;
}
Java 语言(一种计算机语言，尤用于创建网站)
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the NGE for the
// given circular array arr[]
static void printNGE(int arr[], int n)
{
// Initialize stack and nge[] array
Stack<Integer> s = new Stack<>();
int nge[] = new int[n];
int i = 0;
// Initialize nge[] array to -1
for(i = 0; i < n; i++)
{
nge[i] = -1;
}
i = 0;
// Traverse the array
while (i < 2 * n)
{
// If stack is not empty and
// current element is greater
// than top element of the stack
while (!s.isEmpty() &&
arr[i % n] > arr[s.peek()])
{
// Assign next greater element
// for the top element of the stack
nge[s.peek()] = arr[i % n];
// Pop the top element
// of the stack
s.pop();
}
s.push(i % n);
i++;
}
// Print the nge[] array
for(i = 0; i < n; i++)
{
System.out.print(nge[i] + " ");
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 4, -2, 5, 8 };
int N = arr.length;
// Function Call
printNGE(arr, N);
}
}
// This code is contributed by yashbeersingh42
Python 3
# Python3 program for the above approach
# Function to find the NGE for the
# given circular array arr[]
def printNGE(arr, n) :
# create stack list
s = [];
# Initialize nge[] array to -1
nge = [-1] * n;
i = 0;
# Traverse the array
while (i < 2 * n) :
# If stack is not empty and
# current element is greater
# than top element of the stack
while (len(s) != 0 and arr[i % n] > arr[s[-1]]) :
# Assign next greater element
# for the top element of the stack
nge[s[-1]] = arr[i % n];
# Pop the top element
# of the stack
s.pop();
s.append(i % n);
i += 1;
# Print the nge[] array
for i in range(n) :
print(nge[i], end= " ");
# Driver Code
if __name__ == "__main__" :
arr = [ 4, -2, 5, 8 ];
N = len(arr);
# Function Call
printNGE(arr, N);
# This code is contributed by AnkitRai01
C
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the NGE for the
// given circular array []arr
static void printNGE(int []arr, int n)
{
// Initialize stack and nge[] array
Stack<int> s = new Stack<int>();
int []nge = new int[n];
int i = 0;
// Initialize nge[] array to -1
for(i = 0; i < n; i++)
{
nge[i] = -1;
}
i = 0;
// Traverse the array
while (i < 2 * n)
{
// If stack is not empty and
// current element is greater
// than top element of the stack
while (s.Count != 0 &&
arr[i % n] > arr[s.Peek()])
{
// Assign next greater element
// for the top element of the stack
nge[s.Peek()] = arr[i % n];
// Pop the top element
// of the stack
s.Pop();
}
s.Push(i % n);
i++;
}
// Print the nge[] array
for(i = 0; i < n; i++)
{
Console.Write(nge[i] + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 4, -2, 5, 8 };
int N = arr.Length;
// Function Call
printNGE(arr, N);
}
}
// This code is contributed by 29AjayKumar
java 描述语言
<script>
// Javascript program for the above approach
// Function to find the NGE for the
// given circular array []arr
function printNGE(arr, n)
{
// Initialize stack and nge[] array
let s = [];
let nge = new Array(n);
let i = 0;
// Initialize nge[] array to -1
for(i = 0; i < n; i++)
{
nge[i] = -1;
}
i = 0;
// Traverse the array
while (i < 2 * n)
{
// If stack is not empty and
// current element is greater
// than top element of the stack
while (s.length != 0 &&
arr[i % n] > arr[s[s.length - 1]])
{
// Assign next greater element
// for the top element of the stack
nge[s[s.length - 1]] = arr[i % n];
// Pop the top element
// of the stack
s.pop();
}
s.push(i % n);
i++;
}
// Print the nge[] array
for(i = 0; i < n; i++)
{
document.write(nge[i] + " ");
}
}
let arr = [ 4, -2, 5, 8 ];
let N = arr.length;
// Function Call
printNGE(arr, N);
// This code is contributed by suresh07.
</script>
输出:
5 5 8 -1
时间复杂度:O(N) T5辅助空间:** O(N)
版权属于：月萌API www.moonapi.com，转载请注明出处
