Java 中的下一个更大元素

2024年9月10日 | 阅读 9 分钟

在数组中，下一个更大的元素是指最接近且大于当前元素的元素。另外，下一个更大的元素应该出现在当前元素的后面。任务是返回整数数组中每个元素的下一个更大的元素。如果数组中的某个元素的下一个更大元素不存在，则为此元素打印适当的消息。为简单起见，我们假设输入数组中的所有元素都非负。让我们通过一个例子来理解。

输入

arr[] = {14, 16, 9, 90, 99, 2, 6, 19, 4}

带解释的输出

元素	下一个更大的元素（NGE）	原因
14	16	元素 16 紧跟在 14 后面。此外，16 大于 14。
16	90	大于 16 的元素是 90 和 99。但是，我们将选择 90，因为元素 90 是最接近元素 16 的。
9	90	元素 90 紧跟在 9 后面。此外，90 大于 9。
90	99	元素 99 紧跟在 90 后面。此外，99 大于 90。
99	未找到	在元素 99 之后没有比 99 更大的元素了。
2	6	元素 6 紧跟在 2 后面。此外，6 大于 2。
6	19	元素 19 紧跟在 6 后面。此外，19 大于 6。
19	未找到	在元素 19 之后没有比 19 更大的元素了。
4	未找到	在元素 4 之后没有其他元素了。

注意 1：对于最后一个元素，下一个更大的元素将始终是 -1，因为在最后一个元素之后，我们没有其他元素了。

注意 2：对于按非递增顺序排序的输入数组，下一个更大元素的值将始终为 -1。这是因为从当前元素开始的下一个元素将始终小于或等于当前元素，因为元素是按非递减顺序排列的。

例如

输入

arr[] = {89, 60, 58, 45, 39, 36, 20}

带解释的输出

输入数组所有元素的下一个更大元素都是 -1。

对于数字 89，没有元素出现在 89 之后且大于 89。

对于数字 60，没有元素出现在 60 之后且大于 60。

对于其他元素也可以给出类似的解释。

方法

有两种方法可以解决下一个更大的元素问题：一种是朴素方法，另一种是使用堆栈。让我们从朴素方法开始。

朴素方法

朴素方法很简单。你需要使用两个 for 循环。外层循环用于选择元素，内层循环用于将元素与选定的元素（当前元素）进行比较。当找到一个更大的元素（与当前元素比较后）时，内层循环会立即终止。观察以下程序。

文件名： NGE.java

public class NGE
{

// main method
public static void main(String argvs[])
{
// input array
int arr[] = new int[]{14, 16, 9, 90, 99, 2, 6, 19, 4};

// computing size of the input array
int size = arr.length;

System.out.println("The input array is: ");
for(int i = 0; i < size; i++)
{
System.out.print(arr[i] + " ");
}
System.out.println("\n");

for(int i = 0; i < size; i++)
{
int temp = -1;
for(int j = i + 1; j < size; j++)
{
    if(arr[j] > arr[i])
    {
       temp = arr[j]; 
       break;
    }
    
}
if(temp != -1)
{
System.out.println("The next greater element for the element " + arr[i] + " is: " + temp);
}
else
{
System.out.println("The next greater element for the element " + arr[i] + " does not exist. ");
}
}
}
}

输出

The input array is: 
14 16 9 90 99 2 6 19 4 

The next greater element for the element 14 is: 16
The next greater element for the element 16 is: 90
The next greater element for the element 9 is: 90
The next greater element for the element 90 is: 99
The next greater element for the element 99 does not exist. 
The next greater element for the element 2 is: 6
The next greater element for the element 6 is: 19
The next greater element for the element 19 does not exist. 
The next greater element for the element 4 does not exist.

时间复杂度：上面的程序使用了两个嵌套的 for 循环。因此，该程序的 time complexity 为 O(n²)，其中 n 是输入数组中元素的总数。

空间复杂度：该程序没有使用任何额外的空间。因此，该程序的 space complexity 为 O(1)。

优化方法：使用堆栈

算法

步骤 1：将第一个元素压入堆栈。

步骤 2：逐个选择剩余的元素，并在循环中重复提到的子步骤。

将当前元素视为下一个。
如果堆栈不为空，则比较堆栈的顶部元素和下一个元素。
如果下一个元素大于堆栈的顶部元素，则从堆栈中弹出该元素。下一个元素是弹出元素的下一个更大的元素。
如果弹出的元素小于下一个元素，则继续从堆栈中弹出元素。对于所有这些弹出的元素，下一个元素将成为下一个更大的元素。

步骤 3：最终，堆栈中的下一个元素被压入。

步骤 4：在步骤 2 中提到的循环完成后，继续从堆栈中弹出所有剩余的元素，并为它们显示 -1，因为它们没有下一个更大的元素。

文件名： NGE1.java

public class NGE1 
{
// internal class that imitates a stack
public class Stk 
{
int t;
int store[] = new int[100];

// Stack method that is being used by the displayNGE() method
void push(int y)
{
    if (t == 99)
    {
        System.out.println("Stack is full");
    }
    else
    {
        t = t + 1;
        store[t] = y;
    }
}

int pop()
{
    if (t == -1)
    {
        System.out.println("the stack is underflow");
        return -1;
    }
    else 
    {
        int ele = store[t];
        t = t - 1;
        return ele;
    }
}

boolean isVacant()
{
    return (t != -1) ? false : true;
}
}

// displays the pair of elements and the next greater element for
// all of the elements of the arr[] of the size s
public void displayNGE(int arr[], int s)
{
int j = 0;
Stk stk = new Stk();
stk.t = -1;
int ele;
int next;

/* push the first element to the stack */
stk.push(arr[0]);

// loop over for the rest of elements
for (j = 1; j < s; j++)
{
    next = arr[j];

    if (stk.isVacant() == false)
    {

        // if the stack is not empty, then
        // pop the element from stack
        ele = stk.pop();

        // If the popped element is smaller than
        //  the  next, then a) print the poppped element and the next greater element
        // b) keep popping from the stack until 
        // the elements are smaller andthe stack is not vacant
        while (ele < next)
        {
            System.out.println("The next greater element for the element " + ele + " is: " + next);
            if (stk.isVacant() == true)
            {
                break;
            }
            ele = stk.pop();
        }

        // If the ele is larger than the next, then
        //   push back the element back
        if (ele > next)
        {
            stk.push(ele);
        }
    }

    // push the next to the stack stk. hus, we can look for the next
    // larger element for it 
    stk.push(next);
}

// The next greater element does not exist for the left elements
// in the stack stk, so we shall display the message accordingly 
// for all these left elements
while (stk.isVacant() == false)
{
    ele = stk.pop();
    System.out.println("The next greater element for the element " + ele + " does not exist.");
}
}

// main method
public static void main(String argvs[])
{

// creating an object of the class NGE1
NGE1 obj = new NGE1();

// input array
int arr[] = new int[]{14, 16, 9, 90, 99, 2, 6, 19, 4};

// computing size of the input array
int size = arr.length;

System.out.println("The input array is: ");
for(int i = 0; i < size; i++)
{
System.out.print(arr[i] + " ");
}
System.out.println("\n");

obj.displayNGE(arr, size);

}
}

输出

The input array is: 
14 16 9 90 99 2 6 19 4 

The next greater element for the element 14 is: 16
The next greater element for the element 9 is: 90
The next greater element for the element 16 is: 90
The next greater element for the element 90 is: 99
The next greater element for the element 2 is: 6
The next greater element for the element 6 is: 19
The next greater element for the element 4 does not exist.
The next greater element for the element 19 does not exist.
The next greater element for the element 99 does not exist.

时间复杂度：该程序的 time complexity 为 O(n)，其中 n 是数组中元素的总数。

空间复杂度：该程序的 space complexity 为 O(n)，其中 n 是数组中元素的总数。

我们看到输出中数字出现的顺序与输入数组中的顺序不同。为了保持顺序，需要反向遍历。观察以下程序。

文件名： NGE2.java

// important import statement
import java.util.Stack;

public class NGE2
{

// displays the pair of elements and the next greater element for
// all of the elements of the arr[] of the size s
public void displayNGE(int a[], int s)
{
Stack<Integer> stk = new Stack<Integer>();
int nextGrInt[] = new int[a.length];

// iterate over the remaining elements
for (int j = a.length - 1; j >= 0; j--)
{
    // if the stack is not vacant, then pop
    // an element from the stack.
    // If the element popped is less
    // than the next, then first display the 
    // element and the next greater element
    // and secondly keep popping the element 
    // till the elements are empty and the stack
    // is not vacant
    if (!stk.empty())
    {
        while (!stk.empty()
               && stk.peek() <= a[j])
        {
            stk.pop();
        }
    }
    nextGrInt[j] = stk.empty() ? -1 : stk.peek();
    stk.push(a[j]);
}
for (int j = 0; j < a.length; j++)

    if(nextGrInt[j] != -1)
    {
    System.out.println("The next greater element for the element " + a[j] + " is: " + nextGrInt[j]);
    }
    else
    {
    System.out.println("The next greater element for the element " + a[j] + " does not exist.");
    }
}


// main method
public static void main(String argvs[])
{

// creating an object of the class NGE2
NGE2 obj = new NGE2();

// input array
int arr[] = new int[]{14, 16, 9, 90, 99, 2, 6, 19, 4};

// computing size of the input array
int size = arr.length;

System.out.println("The input array is: ");
for(int i = 0; i < size; i++)
{
System.out.print(arr[i] + " ");
}
System.out.println("\n");


obj.displayNGE(arr, size);


}
}

输出

The input array is: 
14 16 9 90 99 2 6 19 4 

The next greater element for the element 14 is: 16
The next greater element for the element 16 is: 90
The next greater element for the element 9 is: 90
The next greater element for the element 90 is: 99
The next greater element for the element 99 does not exist.
The next greater element for the element 2 is: 6
The next greater element for the element 6 is: 19
The next greater element for the element 19 does not exist.
The next greater element for the element 4 does not exist.

时间复杂度：该程序的 time complexity 为 O(n)，其中 n 是数组中元素的总数。

空间复杂度：该程序的 space complexity 为 O(n)，其中 n 是数组中元素的总数。

下一个主题Java 中的星形数字

← 上一个下一个 →

Java 中的下一个更大元素

注意 1：对于最后一个元素，下一个更大的元素将始终是 -1，因为在最后一个元素之后，我们没有其他元素了。

注意 2：对于按非递增顺序排序的输入数组，下一个更大元素的值将始终为 -1。这是因为从当前元素开始的下一个元素将始终小于或等于当前元素，因为元素是按非递减顺序排列的。

方法

朴素方法

优化方法：使用堆栈

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的下一个更大元素

注意 1：对于最后一个元素，下一个更大的元素将始终是 -1，因为在最后一个元素之后，我们没有其他元素了。

注意 2：对于按非递增顺序排序的输入数组，下一个更大元素的值将始终为 -1。这是因为从当前元素开始的下一个元素将始终小于或等于当前元素，因为元素是按非递减顺序排列的。

方法

朴素方法

优化方法：使用堆栈

相关帖子

Java 中不相邻元素的最大总和

DecimalStyle toString() Method in Java with Examples

Java 中显示带 GMT 和 UTC 的时区列表

哪个组件负责运行 Java 程序

Java 中的 RegionMatches() 方法

Java 中设置默认关闭操作

Java 程序获取集合的大小并验证集合是否为空

Java 中的递增和递减运算符

Java 中的自定义类

Java 中的确定赋值

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器