072每日温度

每日温度题目链接https://leetcode.cn/problems/daily-temperatures/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答//方法单调栈 //时间复杂度O(n) //空间复杂度O(n) public int[] dailyTemperatures(int[] temperatures) { int n temperatures.length; DequeInteger stack new LinkedList(); int[] ans new int[n]; Arrays.fill(ans,0); for(int i0; in; i){ //清算比当前温度小的所有温度 while(!stack.isEmpty() temperatures[i] temperatures[stack.peek()]){ int top stack.pop(); ans[top] i - top; } stack.push(i); } return ans; }分析代码的时间复杂度为O(n)空间复杂度为O(n)。解题思路采用单调栈栈中存储下标满足从栈底到栈顶的下标对应的温度列表中的温度依次递减。当遇到不满足递减的温度时就可以弹出所有对应温度比当前温度小的下标并根据下标清算这些弹出元素的答案。看了官方题解后的解答//官方的思路与解答与我的解答完全一致故不重复赘述分析无。总结本题主要需要掌握单调栈的应用。