本文共 1181 字,大约阅读时间需要 3 分钟。
题目:
Given a list of daily temperatures
For example, given the list of temperaturesT
, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put0
instead.T = [73, 74, 75, 71, 69, 72, 76, 73]
, your output should be[1, 1, 4, 2, 1, 1, 0, 0]
. Note: The length of temperatures will be in the range[1, 30000]
. Each temperature will be an integer in the range[30, 100]
.
解释:
用栈做,维护一个降序的栈,栈中存储的是index
,index
本身不是降序的,但是index
对应的T[index]
是降序的,当出现比栈中一些index
对应的T[index]
大的T[i]
的时候,把那些index
出栈,并保存好位置差,然后把当前的i
压入栈,这样就可以实现要求。 python代码: class Solution: def dailyTemperatures(self, T): """ :type T: List[int] :rtype: List[int] """ ans=[0]*len(T) stack=[] for i in range(len(T)): while stack and T[stack[-1]]
c++代码:
#includeusing namespace std;class Solution { public: vector dailyTemperatures(vector & T) { stack _stack; int n=T.size(); vector result(n,0); for(int i=0;i
总结:
while
的时候可以多加一些判断。 转载地址:http://oglcn.baihongyu.com/