5 2 votes
Article Rating
Subscribe
提醒
guest
4 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments
sunznx
// CreateTime: 2020-11-22 02:13:20
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        int len = T.size();


        stack<pair<int, int>> s;
        vector<int> ans(len);
        
        for (int i = len-1; i >= 0; i--) {
            auto num = T[i];
            
            while (s.size() && num >= s.top().second) {
                s.pop();
            }
            
            if (s.size() == 0) {
                ans[i] = 0;
            } else {
                ans[i] = s.top().first - i;
            }
            
            s.push({i, num});
        }
        
        return ans;
    }
};


暴走的楚狂

别人都是用list当stack做的,我用字典当stack

# python
from collections import defaultdict

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        result_list = [0] * len(T)
        if len(T) <= 1: return [0]
        tempratures_dict = defaultdict(list)
        tempratures_dict[T[0]].append(0)
        for index, value in enumerate(T[1:]):
            for temprature in list(tempratures_dict.keys()):
                if temprature < value:
                    for date in tempratures_dict[temprature]:
                        result_list[date] = index - date + 1
                    del tempratures_dict[temprature]
            
            tempratures_dict[value].append(index+1)
        return result_list

王半仙儿

给老铁赞一个,正想着python版本的解题呢,你这出了一个👍

王半仙儿

一年前写过,先来占个沙发,晚上用Python来一遍:

class Solution {
    public int[] dailyTemperatures(int[] T) {
        int length = T.length;
        int[] ans = new int[length];
        Deque<Integer> stack = new LinkedList<Integer>();
        for (int i = 0; i < length; i++) {
            int temperature = T[i];
            while (!stack.isEmpty() && temperature > T[stack.peek()]) {
                int prevIndex = stack.pop();
                ans[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }
        return ans;
    }
}