计算在每一天需要等几天才会上涨

每日温度”类似的题目，即找到每个元素在数组中下一个更大的元素的距离。这种问题通常可以使用单调栈**来优化，保持栈中的元素单调递减，并在遇到更大的元素时进行出栈操作。

package org.example;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Main {

    public static void main(String[] args) {
        List<Integer> stockPrices = getNums();
        int[] result = calculateDaysToRise(stockPrices);

        // 打印结果
        for (int days : result) {
            System.out.print(days + " ");
        }
    }

    // 计算每一天需要等待多少天才会有更高的股价
    public static int[] calculateDaysToRise(List<Integer> stock) {
        int n = stock.size();
        int[] result = new int[n]; // 默认初始化为 0
        Stack<Integer> stack = new Stack<>();

        // 遍历所有股价
        for (int i = 0; i < n; i++) {
            // 栈顶元素比当前元素小，表示找到下一个更高的股价
            while (!stack.isEmpty() && stock.get(i) > stock.get(stack.peek())) {
                int idx = stack.pop();
                result[idx] = i - idx; // 计算等待天数
            }
            // 当前元素入栈
            stack.push(i);
        }

        return result;
    }

    // 示例输入数据
    public static List<Integer> getNums() {
        List<Integer> nums = new ArrayList<>();
        nums.add(30);
        nums.add(40);
        nums.add(50);
        nums.add(60);
        return nums;
    }
}

单调栈的使用：

栈中存储的是元素的索引，在遇到更大的元素时进行出栈，并更新结果数组。
遍历完成后，栈中剩下的元素都没有更大的元素，因此不需要额外处理。

复杂度分析

时间复杂度：O(N)，其中 N 是股价数组的长度。每个元素最多被入栈和出栈一次。
空间复杂度：O(N)，用于存储栈和结果数组。

通过这些优化，代码变得更加简洁、高效，同时性能和内存利用也得到了提升。