LeetCode·739.每日温度·递减栈

链接：https://leetcode.cn/problems/daily-temperatures/solution/bao-li-by-xun-ge-v-uw2h/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

 

示例

 

思路

解题思路

• 暴力循环+双指针

定义两个指针，一个快指针，一个慢指针，慢指针每次遍历一个元素，快指针每次寻找第一个比慢指针指向元素大的元素，最后保存即可，但是会超时

• 递减栈

引入递减栈的概念，我们遍历整个数组，将数组元素下标入栈，每次入栈前判断栈顶元素与当前大小

• 栈顶元素大于当前元素

将当前元素入栈，维持递减性

• 栈顶元素小于当前元素

将栈顶元素弹出，并对相应下标数组保存当前元素与其差值，维持递减性

代码

时间空间复杂度