input: 1, 2, 3, 2, 3
output: 4, 3, 1, 1, 0
answer -1로 초기화
answer = {-1, -1, -1, -1, -1}
스택 원소 <가격, 가격 배열 내 인덱스>
스택 내 원소 오름차순 유지 하도록 push
pop할 때 떨어지지 않은 시간(answer)계산 = 현재 인덱스(i) - 가격 배열 내 인덱스
스택에 남은 모든 원소 하나씩 pop하기
pop할 때 떨어지지 않은 시간(answer)계산 = 마지막 인덱스(4) - 가격 배열 내 인덱스
#include <string>
#include <vector>
#include <stack>
using namespace std;
vector<int> solution(vector<int> prices) {
int N = prices.size();
vector<int> answer(N, -1);
stack<pair<int, int>> st;
for(int i = 0; i<N; ++i){
while(!st.empty() && (st.top().first > prices[i])){
answer[st.top().second] = i - st.top().second;
st.pop();
}
st.push({prices[i], i});
}
while(!st.empty()){
answer[st.top().second] = N-1 - st.top().second;
st.pop();
}
return answer;
}