[LeetCode] 739. Daily Temperatures

轉自LeetCode

Given a list of daily temperatures, produce a list 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 temperatures = [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].

<Solution>

這題和 496. Next Greater Number 的解題想法其實一樣

對每個數，找出在它右邊第一個大於它的數，然後 stack 存的改成 index

然後這題最後的答案，就是計算出那個數離自己有多遠即可

code如下

C++

	class Solution {
	public:
	vector<int> dailyTemperatures(vector<int>& temperatures) {
	const int len = temperatures.size();
	stack<int> stack;
	vector<int> ans(len);
	for(int i = len - 1; i >= 0; i--) {
	while(!stack.empty() && temperatures[stack.top()] <= temperatures[i]) {
	stack.pop();
	}
	ans[i] = stack.empty() ? 0 : stack.top() - i;
	stack.push(i);
	}
	return ans;
	}
	};

view raw dailyTemperuratures.cpp hosted with ❤ by GitHub

Java

	class Solution {
	public int[] dailyTemperatures(int[] temperatures) {
	Stack<Integer> stack = new Stack<>();
	int[] ans = new int[temperatures.length];
	for(int i = temperatures.length - 1; i >= 0; i--) {
	while(!stack.empty() && temperatures[stack.peek()] <= temperatures[i]) {
	stack.pop();
	}
	ans[i] = stack.empty() ? 0 : stack.peek() - i;
	stack.push(i);
	}
	return ans;
	}
	}

view raw dailyTemperuratures.java hosted with ❤ by GitHub

kotlin

	class Solution {
	fun dailyTemperatures(temperatures: IntArray): IntArray {
	val stack = mutableListOf<Int>()
	val ans = IntArray(temperatures.size)
	for(i in temperatures.lastIndex downTo 0) {
	while(stack.isNotEmpty() && temperatures[i] >= temperatures[stack.last()]) {
	stack.removeAt(stack.lastIndex)
	}
	ans[i] = if(stack.isEmpty()) {
	0
	} else {
	stack.last() - i
	}
	stack.add(i)
	}
	return ans
	}
	}

view raw daily_temperatures.kt hosted with ❤ by GitHub