daily-temperatures

题目:Given a list of daily temperatures T, 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, put 0 instead.

实例:For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0]

第一个思路:暴力搜索,复杂度n^2,好吧超时了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
int len=T.size();
vector<int> wait(len,0);
for(int i=0;i<len-1;i++){
bool ismax=true;
int count=1;
int j;
for(j=i+1;j<len;j++){
if(T[i]<T[j]){
ismax=false;
break;
}
count++;
}
if(ismax){
count=0;
}
wait[i]=count;
}
return wait;
}
};

查看超时测试样例,发现超时的代码输入如下:

我就只有两个没过了,如果出现重复的话,只需要算一个的就好了,剩下的都是不用算,在上一个的基础上减一,优化后的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
int len=T.size();
vector<int> wait(len,0);

for(int i=0;i<len-1;i++){
bool ismax=true;
int count=1;
int j;
if(i>=1&&T[i]==T[i-1]){
wait[i]=wait[i-1]-1;
if(wait[i]<0)
wait[i]=0;
continue;
}
for(j=i+1;j<len;j++){

if(T[i]<T[j]){
ismax=false;
break;
}
count++;
}
if(ismax){
count=0;
}
wait[i]=count;
}
return wait;
}
};

对,就加了这么一行,AC了

其实原题目是想考我用栈来解决这个问题的,想了想还是不知道如何用栈来解决这个问题,就去看了一下博客。

数[73,74,75,71,69,72,76,73]

标[0 , 1 , 2 , 3 , 4 , 5 , 6 , 7]

递减栈[]

1)73来,压入[(73,0)]

2)74来,[(74,1)] 比73大的第一个元素是74,可以直接求出下标之差

3)75来,[(75,2)] 比74大的第一个元素是75

4)71来,栈顶元素75大于71,将71压入,[(75,2),(71,3)]

5)69来,压入[ (75,2),(71,3),(69,4)]

6)72来,大于69,弹出69,即比69大的下一个元素是72, 比71大的下一个是72. [ (75,2),(72,5)]

7)76来, 弹出72,75,说明比72,75大的均为76,[ (76,6) ]

8)73来,压入,栈不空,说明栈里面的元素没有下一个比他们大的,呜呜呜,好聪明的做法呀!

好吧 ,栈,你赢了。复杂度几乎是O(n),抱头痛哭。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& T) {
int len=T.size();
vector<int> wait(len,0);
stack<int> s;
int i=0;
while(i<len){
if(s.empty()){
s.push(i);
i++;
}
if(T[i]>T[s.top()]){
while(!s.empty()&&T[i]>T[s.top()]){
wait[s.top()]=i-s.top();
s.pop();
}
s.push(i);
i++;
}else{
s.push(i);
i++;
}
}
while(!s.empty()){
wait[s.top()]=0;
s.pop();
}
return wait;
}
};