株価
13003 ワード
🔒 質問する
🔑 に答える
import java.util.stream.IntStream;
class Solution {
public int[] solution(int[] prices) {
for (int index = 0; index < prices.length ; index++) {
int targetPrice = prices[index];
// 나보다 가장 가까운 작은애 index 찾기, 만약에 못찾으면 -1
int nextLowerPriceIndex = IntStream.range(index, prices.length)
.filter(i->prices[i] < targetPrice)
.findFirst()
.orElse(-1);
// 나와 작은놈의 거리
// 나보다 작은놈 없던데? -> 전체 길이 - 내 현재위치 - 1
// 찾았어! -> 그놈 위치 - 내 위치
int distance = (nextLowerPriceIndex == -1) ? prices.length - index - 1 : nextLowerPriceIndex - index;
prices[index] = distance;
}
return prices;
}
}
🔧 プールの最適化
import java.util.Stack;
public class Solution2 {
public int[] solution(int[] prices) {
// stack 에는 time Stack Index 를 담는다. (유지가 잘되고 있는 애들의 시간)
// index 는 자리로 시간과 비례한다.
// prices[stackIndex.top] = index - stackIndex.pop
var timeStack = new Stack<Integer>();
timeStack.push(0);
// 가격이 떨어지는 애들 라운드별로 검사
for (int index = 1; index < prices.length ; index++) {
// 가격이 떨어진 애 -> 유지 못했으므로 바로 현재 index - timeStackIndex.top == 현재 위치 - 최근까지 크다고 유지된놈의 위치
// index - timeStackIndex.pop 을 스택이 비지 않을 떄 까지 (과거 놈들) && 더 prices[index] < timeIndex.top 일 때까지 쭉 처리해줌.
while (!timeStack.empty() && prices[timeStack.peek()] > prices[index]) {
int recentElementIndex = timeStack.pop();
prices[recentElementIndex] = index - recentElementIndex;
}
// 일단 이 단계까지는 그대로 유지된 경우
timeStack.push(index);
}
// 가격이 떨어지지 않는 놈들은 모두 stack 에 담음.
// stack 남아있는 친구들은 마지막까지 유지된 놈들임
// 따라서 prices[stack.top] = prices.length - stack.top - 1
while (!timeStack.empty()) {
var remainTimeIndex = timeStack.pop();
prices[remainTimeIndex] = prices.length - remainTimeIndex - 1;
}
return prices;
}
// test용 코드
public static void main(String[] args) {
var testArray = new int[]{1,2,3,2,3};
var answerArray = new Solution2().solution(testArray);
// 43110
for (int element : answerArray) {System.out.print(element);}
}
}
Reference
この問題について(株価), 我々は、より多くの情報をここで見つけました https://velog.io/@milkcoke/주식가격テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol