Hot100——739.每日温度

解题思路本题的解题思路其实是需要用到单调栈。本题中用到的是单调递减栈那我们如何来进行使用呢以所给示例进行分析:temperatures [73, 74, 75, 71, 69, 72, 76, 73]输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]首先构造一个空栈切记栈中存储的是数组元素的下标遍历temperatures数组将第一个数73的下标置于栈顶而后比较temperatures数组中每一个元素与栈顶元素的大小倘若当前数组元素的大小是大于当前栈顶元素的话则不入栈因为此时不符合递减栈的要求需要弹出栈顶元素直到当前数组元素是小于栈顶元素满足单调栈的条件此时求出相应的下标差就是对应的距离。举例如下设栈为st1.st为空遍历temperatures数组将数组的第一个元素的下标压入堆栈记st[0] 0;此时的堆栈02.i1,取temperatures[1]747473此时若是压入栈则不满单调栈的条件因此弹出栈顶元素计算二者的下标差就是题中所求。所以res[0] 1 - 0 1而后把当前数组元素的下标压入栈中。此时的堆栈13.i2取temperatures[2]757574与2一致弹出栈顶元素将当前数组元素下标存入堆栈中因此res[1] 2 - 1 1;此时的堆栈24.i3取temperatures[3]717175当前数组元素大小小于栈顶元素满足单调递减栈存入堆栈此时栈顶元素是3此时的堆栈2 35.i4取temperatures[4]696971与4一致此时栈顶元素是4此时的堆栈2 3 46.i5取temperatures[5]727269与2一致弹出当前栈顶元素记录res[4] 5 - 4 1继续比较72 71与上述一致res[3] 5 - 3 2继续比较72 75满足单调递减栈压入堆栈栈顶元素是5此时的堆栈2 57.i6取temperatures[6]767672弹出栈顶元素res[5] 6 - 5 1;继续比较7675弹出栈顶元素res[2] 6 - 2 4;将76存入堆栈栈顶元素是6此时的堆栈68.i7取temperatures[7]737376满足单调栈更新栈顶元素为7。此时的堆栈6 7遍历结束。以上便是总体流程。代码Cclass Solution { public: vectorint dailyTemperatures(vectorint temperatures) { int n temperatures.size(); vectorint result(n,0); stackint st; for(int i0; in; i) { while(!st.empty() temperatures[i] temperatures[st.top()]) { auto t st.top(); st.pop(); result[t] i - t; } st.push(i); } return result; } };pythonclass Solution(object): def dailyTemperatures(self, temperatures): :type temperatures: List[int] :rtype: List[int] length len(temperatures) stack [] res [0]*length for i in range(length): while stack and temperatures[i] temperatures[stack[-1]]: t stack.pop() res[t] i - t stack.append(i) return res参考LeetCode 图解 | 739.每日温度