根据往后 n 天的天气预报,计算每一天需要等待几天才会出现一次更高的气温,如果往后都没有更高的气温,则用 0 补位。
例如往后三天的气温是 [1,2,3] , 则输出 [1,1,0]
数据范围: ,每天的温度会满足
[1,2,3]
[1,1,0]
[2,4,5,9,10,0,9]
[1,1,1,1,0,1,0]
[3,1,4]
[2,1,0]
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 每日温度 * @param dailyTemperatures int整型vector * @return int整型vector */ vector<int> temperatures(vector<int>& dailyTemperatures) { // write code here //用单调栈 int n =dailyTemperatures.size(); vector<int> res(n); stack<int> st; for(int i=0;i<n;i++){ while(!st.empty()&&dailyTemperatures[i]>dailyTemperatures[st.top()]){ int index =st.top();//栈顶的下标 res[index] =i-index; st.pop(); } st.push(i);//i的温度小于栈顶的温度 或者栈为空 进栈 } return res; } };/*
func temperatures( temperatures []int ) []int { // write code here var ret []int = make([]int , len(temperatures)) var a []int for k , v := range temperatures { if k == 0 { a = append( a , k ) continue } if v > temperatures[k - 1] { i := len(a) - 1 for i >= 0 && temperatures[a[i]] < v{ ret[ a[i] ] = k - a[i] a = a[ : len(a) - 1 ] i-- } } a = append( a , k ) } return ret }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param temperatures int整型一维数组 * @return int整型一维数组 */ public int[] temperatures (int[] temperatures) { // write code here Stack<Integer> stack = new Stack<>(); int[] res = new int[temperatures.length]; for(int i = 0; i < temperatures.length; i++){ if(stack.isEmpty() || temperatures[stack.peek()] > temperatures[i]){ stack.push(i); }else{ if(temperatures[stack.peek()] == temperatures[i]){ stack.push(i); }else{ while(!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){ int cur = stack.pop(); res[cur] = i - cur; } stack.push(i); } } } // 因为res的初始值本来就是0,此步骤可以不要,但为了流程完整性,还是写上 while(!stack.isEmpty()){ res[stack.pop()] = 0; } return res; } }宏观上看,遍历一遍数组的时间复杂度是O(n)。而弹出栈的元素绝不会再被压回去,所有的元素在整个算法流程中都会来一遍入栈和出栈,因此整体时间复杂度就是O(n)。开辟了一个栈空间来存放数组的索引,因此空间复杂度也为O(n)。
public int[] temperatures (int[] temperatures) { // write code here int[] ans = new int[temperatures.length]; Stack<Integer> stack = new Stack<>(); for(int i = 0; i < temperatures.length; i++){ while(!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i] ){ int temp = stack.pop(); ans[temp] = i-temp; } stack.push(i); } return ans; }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 每日温度 * @param dailyTemperatures int整型vector * @return int整型vector */ vector<int> temperatures(vector<int>& T) { // write code here stack<int> st; // 递增栈 vector<int> result(T.size(),0); st.push(0); for(int i=1;i<T.size();i++){ while(!st.empty()&&T[i]>T[st.top()]){ //注意栈不能为空 result[st.top()]=i-st.top(); st.pop(); } st.push(i); } return result; } };
package main import _"fmt" /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 每日温度 * @param dailyTemperatures int整型一维数组 * @return int整型一维数组 */ func temperatures( dailyTemperatures []int ) []int { n:=len(dailyTemperatures) ans:=make([]int,n) stk:=[]int{} for i,x:=range dailyTemperatures{ for len(stk)>0&&dailyTemperatures[stk[len(stk)-1]]<x{ ans[stk[len(stk)-1]]=i-stk[len(stk)-1] stk=stk[:len(stk)-1] } stk=append(stk,i) } return ans }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 每日温度 * @param dailyTemperatures int整型vector * @return int整型vector */ vector<int> temperatures(vector<int>& dailyTemperatures) { // write code here stack<int> stc; stc.push(0); for(int i=dailyTemperatures.size()-2; i>=0; i--) { if(dailyTemperatures[i] < dailyTemperatures[i+1]) stc.push(1); else stc.push(0); } vector<int> vec; while(!stc.empty()) { vec.push_back(stc.top()); stc.pop(); } // 看错题意了 后面找补了一下 就勉为其难的过了 for(int i=0; i<vec.size(); i++) { if(vec[i] == 1) continue; else { for(int j = i+1; j<vec.size(); j++) { if(dailyTemperatures[j] > dailyTemperatures[i]) { vec[i] = j - i; break; } } } } return vec; } };
public int[] temperatures (int[] dailyTemperatures) { int n = dailyTemperatures.length; int[] res = new int[n]; //最后一个直接为0 res[n - 1] = 0; //从倒数第2个开始向前遍历 for (int i = n - 2; i >= 0; i--) { //从i的后一位开始比较 int j = i + 1; while (j < n) { //如果后一个比当前元素大,则记录距离 if (dailyTemperatures[i] < dailyTemperatures[j]) { res[i] = j - i; break; } else if (res[j] == 0) {//后一位置为0,则说明后面没有比j位置更大温度,则当前遍历的i位置也为0 res[i] = 0; break; } else {//j位置不为0时,则直接下一个位置:为第一个比j位置大的数 j += res[j]; } } } return res; }
class Solution: def temperatures(self , temperatures: List[int]) -> List[int]: # write code here stack, res = [], [0] * len(temperatures) for i in range(len(temperatures)-1, -1, -1): while stack and temperatures[i] >= temperatures[stack[-1]]: stack.pop() if not stack: res[i] = 0 else: res[i] = stack[-1] - i stack.append(i) return res