java - 返回列表中下一个高温的列表

Question

我有一个列表输入:[70,71,74,69,70,76,71,80,70,65]它代表当天的温度，我应该返回一个列表，该列表指示 future 比今天更热的天数。如果没有比现在更热的日子，只需在列表中添加 0。

对于上述输入，预期输出为 [ 1, 1, 3, 1, 1, 2, 1, 0, 0, 0]

澄清必要的工作:我们寻找下一个更高温度的位置。如果没有更高的则返回零。例如Index0 为 70。70 后的下一个温度更高 (71)。所以我们写 1。71 后面跟着 74，所以我们再次写 1。 74 之后是 69 和 70，它们较低，但 76 较高。所以我们写一个3。依此类推...

我能想到的一种方法是使用两个 for 循环并找到下一个更高的值。

        List<Integer> result =  new ArrayList<>(Collections.nCopies(size,0));
        for(int i = 0; i<list.size();i++){
            for(int j=i+1;j<list.size();j++){
                if(list.get(i)<list.get(j)){
                    result.add(i,j-i);
                    break;
                }
            }
        }

上述方法的时间复杂度为O(n^2)。我想知道是否还有其他时间复杂度更好的方法？

Answer 1

我假设您不想知道每个元素与下一个严格更大的元素之间的距离，因为这符合您的预期输出。

简单地使用堆栈，首先将第一个元素插入堆栈，然后从第二个元素开始迭代数组，检查当前元素是否大于堆栈中的顶部元素。如果它大于，则当前索引是堆栈中顶部元素的答案，更新其答案并弹出它，然后对堆栈中新的顶部元素重复。重复此操作，直到栈为空或者当前元素不大于栈顶元素。之后，将当前元素也插入堆栈，以便我们可以找到它的答案并继续迭代。

该方法的复杂度为 O(n)。

这是我在 https://www.geeksforgeeks.org/next-greater-element/ 找到的代码，稍作修改以满足您的具体需求:

//Java program to print next 
//greater element using stack 

import java.util.ArrayList;
import java.util.Collections;

public class NGE
{
    static class stack
    {
        int top;
        int items[] = new int[100];

        // Stack functions to be used by printNGE
        void push(int x)
        {
            if (top == 99)
            {
                System.out.println("Stack full");
            }
            else
            {
                items[++top] = x;
            }
        }

        int pop()
        {
            if (top == -1)
            {
                System.out.println("Underflow error");
                return -1;
            }
            else
            {
                int element = items[top];
                top--;
                return element;
            }
        }

        boolean isEmpty()
        {
            return (top == -1) ? true : false;
        }
    }

    /* prints element and NGE pair for
    all elements of arr[] of size n */
    static void printNGE(int arr[], int n)
    {
        int i = 0;
        stack s = new stack();
        s.top = -1;
        int element, next;

        //answer initialized with zeros
        ArrayList<Integer> answer = new ArrayList<>(Collections.nCopies(n, 0));

        /* push the first element to stack */
        s.push(0);

        // iterate for rest of the elements
        for (i = 1; i < n; i++)
        {
            next = i;

            if (s.isEmpty() == false)
            {

                // if stack is not empty, then
                // pop an element from stack
                element = s.pop();

                /* If the popped element is smaller than 
                next, then a) print the pair b) keep 
                popping while elements are smaller and 
                stack is not empty */
                while (arr[element] < arr[next])
                {
                    answer.set(element, next - element);
                    if (s.isEmpty() == true)
                        break;
                    element = s.pop();
                }

                /* If element is greater than next, then 
                push the element back */
                if (arr[element] > arr[next])
                    s.push(element);
            }

            /* push next to stack so that we can find next 
            greater for it */
            s.push(next);
        }

        System.out.println(answer);
    }

    public static void main(String[] args)
    {
        int arr[] = { 70, 71, 74, 69, 70, 76, 71, 80, 70, 65 };
        int n = arr.length;
        printNGE(arr, n);
    }
}