自学内容网 自学内容网

【栈】Leetcode 739. 每日温度【中等】

每日温度

给定一个整数数组 temperatures ,表示每天的温度,返回一个数组 answer ,其中 answer[i] 是指对于第 i 天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

解题思路

  • 1、使用单调栈来解决问题。
  • 2、遍历温度数组,对于每个温度:
  •  如果栈为空,则将当前索引入栈;
    
  •  如果当前温度大于栈顶温度,则出栈,并计算出栈温度对应的天数差值,并将结果存入结果数组;
    
  •  如果当前温度小于等于栈顶温度,则将当前索引入栈,继续遍历。
    
  • 3、遍历完成后,将栈中剩余元素对应的结果设置为0。

Java实现

public class DailyTemperatures {

    public int[] dailyTemperatures(int[] temperatures) {

        int n = temperatures.length;
        int[] answer = new int[n];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < n; i++) {

            //栈不为空且当前元素值大于栈顶元素,计算最大元素差值
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int prevIndex = stack.pop();
                answer[prevIndex] = i - prevIndex;
            }
            //添加元素,下一个元素比较当前元素值
            stack.push(i);
        }

        return answer;
    }

    public static void main(String[] args) {
        DailyTemperatures solution = new DailyTemperatures();
        int[] temperatures = {73, 74, 75, 71, 69, 76,72,  73};
        int[] result = solution.dailyTemperatures(temperatures);

        System.out.print("Result: [");
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]);
            if (i < result.length - 1) {
                System.out.print(", ");
            }
        }
        System.out.println("]");
    }
}

时间空间复杂度

  • 时间复杂度:O(n),其中n为温度数组temperatures的长度。因为需要遍历温度数组一次,并且每个元素最多入栈一次。

  • 空间复杂度:O(n),使用了一个额外的栈来存储温度数组的索引。


原文地址:https://blog.csdn.net/FLGBgo/article/details/137961765

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!