LeetCode739:每日温度问题解析

问题描述

给定一个整数数组temperatures表示每天的温度，返回一个数组answer，其中answer[i]是等待下一次温度升高所需的天数。如果之后都没有温度升高，则answer[i] == 0。

解题思路

1. 暴力求解: 最直接的方法是使用双重循环。对于每一天，向后查找直到找到一个更高的温度。这种方法的时间复杂度为O(n^2)，效率较低。
2. 单调栈优化: 通过维护一个存储温度下标的递减栈，当遇到更高温度时，弹出栈顶元素并计算等待天数。此方法只需一次遍历，时间复杂度为O(n)。

代码示例

暴力求解:

public int[] dailyTemperatures(int[] temperatures) {    int[] result = new int[temperatures.length];    for (int i = 0; i  temp) {                result[i] = j - i;                break;            }        }    }    return result;}

单调栈优化:

import java.util.Stack;public class Solution {    public int[] dailyTemperatures(int[] temperatures) {        int[] result = new int[temperatures.length];        Stack stack = new Stack<>();        for (int i = 0; i  temperatures[stack.peek()]) {                int index = stack.pop();                result[index] = i - index;            }            stack.push(i);        }        return result;    }}

性能分析

两种方法的性能对比：