对于LeetCode上的股票跨度问题，有更好的解决方案吗？

Question

我做了5/19/2020年5月19日的Leetcode挑战，这是在线股票跨度。其描述是这样的：

编写一个类StockSpanner，它收集某些股票的每日报价，并返回该股票当天价格的跨度。股票今天价格的跨度被定义为股票价格小于或等于当日价格的最大连续天数(从今天开始并向后追溯)。

我使用了一种使用Stack的方法，它包含大小为2的int数组，其中index 0存储价格，index 1存储该价格的跨度。我提交并通过了，但只超过了大约30%的Java提交。然而，在YouTube上找到的解决方案使用了与我相同的方法，使用了几种不同的语言，包括Java和Python。

链接到YouTube解决方案：https://www.youtube.com/watch?v=lGWLBgwd-cw&t=64s

链接到LeetCode：https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/536/week-3-may-15th-may-21st/3334/

有没有人有更好的解决方案？

下面是我的代码：

public class StockSpanner1 {
    Stack<int[]> prices;

    public StockSpanner1() {
        prices = new Stack<>();
    }

    public int next(int price) {
        int span = 1; // All inputs will start with span of 1

        // While the top price is less than the new price, sum the spans
        while (!prices.isEmpty() && prices.peek()[0] <= price) {
            span += prices.pop()[1]; // Sum the spans and pop the top
        }

        prices.push(new int[]{price, span}); // Add the new price with its span

        return span; // Return the span
    }
}

Answer 1

    public class StockSpanner {
        Stack<Node> stack;
        int index;

        public StockSpanner()    //default constructor
        {
           this.stack=new Stack<>();
           this.index=0;
        }

        public int next(int price) {
            while(!stack.isEmpty() && stack.peek().val<=price){
                stack.pop();
            }
            int span=0;
            if(stack.isEmpty())  
                span = index+1;
            else 
                span = index-stack.peek().index+1;
            stack.push(new Node(price,++index));
            return span;
        }
    }

    class Node {
        int val;
        int index;

        public Node(int val,int index){
            this.val=val;
            this.index=index;
        }
    }

这是我的解决方案，希望它能有所帮助。

Answer 2

class solve {

    // Function to calculate span
    // price[]: input array
    public static int[] calculateSpan(int price[], int n) {
        Stack<Integer> stk = new Stack<>();
        HashMap<Integer, Integer> hs = new HashMap<>();
        int ngli[] = new int[n];
        for (int i = 0; i < n; i++) {
            hs.put(price[i], i);
        }

        ngli[0] = -1;
        for (int i = 0; i < n; i++) {

            if (!stk.isEmpty() && stk.peek() > price[i]) {
                ngli[i] = hs.get(stk.peek());
            } else if (!stk.isEmpty() && stk.peek() < price[i]) {
                while (!stk.isEmpty() && stk.peek() < price[i]) {
                    stk.pop();
                }
                if (stk.isEmpty()) {
                    ngli[i] = -1;
                } else {
                    ngli[i] = hs.get(stk.peek());
                }
            }
            stk.push(price[i]);
        }
        for (int i = 0; i < n; i++) {
            if ((i - ngli[i]) > 0) ngli[i] = i - ngli[i];
        }

        return ngli;
    }

}