leetcode - 739. Daily temperature

subject

Code

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

//  Monotonic stack  
vector<int> dailyTemperatures(vector<int>& temperatures) {
    
	int n = temperatures.size();
	vector<int> res(n, 0);
	stack<int> s;
	for(int i = 0; i < n; i++){
    
		while(!s.empty() && temperatures[i] > temperatures[s.top()]){
    
			int index = s.top();
			s.pop();
			res[index] = i - index;
		}
		s.push(i);
	}
	return res;
}

//  Time limit exceeded  
vector<int> dailyTemperatures1(vector<int>& temperatures) {
    
	int n = temperatures.size();
	vector<int> res(n, 0);
	for(int i = 0; i < n - 1; i++){
    
		for(int j = i + 1; j < n; j++){
    
			if(temperatures[i] < temperatures[j]){
    
				res[i] = j - i;
				break;
			}
		}
	}
	return res;
}

int main(){
    
	int n;
	cin>>n;
	vector<int> res;
	vector<int> temperatures(n);
	for(int i = 0; i < n; i++){
    
		cin>>temperatures[i];
	}
	res = dailyTemperatures(temperatures);
	for(int i = 0; i < res.size(); i++){
    
		cout<<res[i]<<" ";
	}
	return 0;
}