https://leetcode.com/problems/daily-temperatures/

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

자신의 오른쪽에 있는 수들 중 큰 값과의 거리 차이를 반환한다. (75 → 76 까지 idx 차이는 4)

뒤 에서 필요 없는 수는 쳐 내가면서 필요한 수만 stack에 쌓아서 비교해 간다.

class Solution {
public:
	vector<int> dailyTemperatures(vector<int>& T) {
		std::stack<int> cmpStack;
		vector<int> save(T.size()); // return 해줄 값
		for (int i = T.size() - 1; i >= 0; --i)
		{
			if (cmpStack.empty()) // 처음에 넣어주기위해.처음에 넣고 시작해도 될듯
			{
				cmpStack.push(i);
				save[i] = 0;
			}				
			else
			{
				int bigIdx = cmpStack.top();  // stack에는 T의 idx가 쌓인다.
				if (T[bigIdx] > T[i])  //  73, 74, 75, 71, 69, 72, 76, 73
				{
					save[i] = bigIdx - i;
					cmpStack.push(i);
				}
				else //  73, 74, 75, 71, 69, 72, 76, 73
				{	
					if (save[bigIdx] == 0) // save에서의 거리가 0이었다면 그 뒤에는 없는거다.
					{
						cmpStack.pop();
						cmpStack.push(i);
						save[i] = 0;
					}
					else
					{
						while (T[bigIdx] <= T[i]) // 같은 값이 나올때도 빼주면서 다음 값 찾는다.
						{
							cmpStack.pop();
							if (cmpStack.empty())
								break;
							bigIdx = cmpStack.top();
						}
						if (cmpStack.empty())
						{
							cmpStack.push(i);
							save[i] = 0;
						}
						else
						{
							save[i] = cmpStack.top() - i;
							cmpStack.push(i);							
						}
					}			
				}
			}
		}
		return save;
	}
};

Runtime: 88 ms, faster than 72.93% of C++ online submissions for Daily Temperatures.

Memory Usage: 39.9 MB, less than 95.83% of C++ online submissions for Daily Temperatures.

Runtime: 80 ms, faster than 75.03% of C++ online submissions for Daily Temperatures.

Memory Usage: 39.9 MB, less than 99.00% of C++ online submissions for Daily Temperatures.

대체로 비슷한 결과를 얻었다.