代码随想录 -- 单调栈 -- 每日温度

单调栈

适用场景

一维数组中，求任意元素左边（右边）第一个比他大（小）的元素的位置。

使用时明确

单调栈中存放的是数组下标

单调栈是递增还是递减

每日温度

739. 每日温度 - 力扣（LeetCode）

思路：

题目中要求当前元素的右边比当前元素大的第一个元素的位置，所以单调栈是递增的，单调栈中存放数组下标。

首先将下标0加入单调栈中，从下标1开始遍历：

• 当temperatures[i]>temperatures[st.top()]：下标为i的元素就是比下标为st.top()的元素大的第一个元素，故res[i]=i-st.top()，弹出栈顶元素，直到栈顶元素大于等于当前元素时，将当前元素加入单调栈中。
• 如果temperatures[i]<=temperatures[st.top()]：下标为i的元素比下标为st.top()的元素还小，直接将下标i加入单调栈中。

class Solution(object):
    def dailyTemperatures(self, temperatures):
        n=len(temperatures)
        res=[0]*n
        st=[0]
        for i in range(1,n):
            if temperatures[i] <= temperatures[st[-1]]:
                st.append(i)
            else:
                while st and temperatures[i] > temperatures[st[-1]]:
                    res[st[-1]]=i-st[-1]
                    st.pop()
                st.append(i)
        return res