739. Daily Temperatures

leetcode medium

#array#csharp#leetcode#medium#stack

Task

Задав массив целых чисел temperature, представляющих дневные температуры, верните массив answer, такой, что answer[i] - это количество дней, которые нужно подождать после i-го дня, чтобы температура стала теплее. Если в будущем не существует дня, для которого это возможно, сохраните answer[i] == 0.

Пример:

Input: temperatures = [73,74,75,71,69,72,76,73]

Output: [1,1,4,2,1,1,0,0]

C# solution

matched/original

public class Solution {
    public int[] DailyTemperatures(int[] T) {
        int n = T.Length;
        int[] answer = new int[n];
        Stack<int> stack = new Stack<int>();
        
        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && T[i] > T[stack.Peek()]) {
                int j = stack.Pop();
                answer[j] = i - j;
            }
            stack.Push(i);
        }
        
        return answer;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& DailyTemperatures(vector<int>& T) {
        int n = T.size();
        vector<int>& answer = new int[n];
        stack<int> stack = new stack<int>();
        
        for (int i = 0; i < n; i++) {
            while (stack.size() > 0 && T[i] > T[stack.Peek()]) {
                int j = stack.pop();
                answer[j] = i - j;
            }
            stack.push(i);
        }
        
        return answer;
    }
}

Java solution

matched/original

public class Solution {
    public int[] dailyTemperatures(int[] T) {
        int n = T.length;
        int[] answer = new int[n];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                int j = stack.pop();
                answer[j] = i - j;
            }
            stack.push(i);
        }
        
        return answer;
    }
}

JavaScript solution

matched/original

var dailyTemperatures = function(T) {
    const answer = Array(T.length).fill(0);
    const stack = [];
    
    for (let i = 0; i < T.length; i++) {
        while (stack.length && T[i] > T[stack[stack.length - 1]]) {
            const j = stack.pop();
            answer[j] = i - j;
        }
        stack.push(i);
    }
    
    return answer;
};

Python solution

matched/original

def dailyTemperatures(T):
    n = len(T)
    answer = [0] * n
    stack = []
    
    for i in range(n):
        while stack and T[i] > T[stack[-1]]:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    
    return answer

Go solution

matched/original

vpackage main

func dailyTemperatures(T []int) []int {
    n := len(T)
    answer := make([]int, n)
    stack := []int{}
    
    for i := 0; i < n; i++ {
        for len(stack) > 0 && T[i] > T[stack[len(stack)-1]] {
            j := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            answer[j] = i - j
        }
        stack = append(stack, i)
    }
    
    return answer
}

Explanation

Algorithm

Создайте стек для хранения индексов дней с температурами, для которых еще не найден более теплый день.

Пройдите по массиву температур и для каждого дня: Пока текущая температура больше температуры дня на вершине стека, обновляйте массив ответов и удаляйте вершину стека. Добавьте текущий день в стек.

Возвращайте массив ответов.

😎