무한 알고리즘 의 주식 가격 범위 (단조 창고 + HashMap)
8322 단어 무한 알고리즘 시리즈
오늘 주식 가격 의 경 계 는 주식 가격 이 오늘 가격 보다 작 거나 같은 최대 연속 일수 로 정의 된다.
예 를 들 어 앞으로 7 일 동안 주식 의 가격 이 [100, 80, 60, 70, 60, 75, 85] 라면 주식 의 경 계 는 [1, 1, 1, 2, 1, 4, 6] 이 될 것 이다.
예시:
입력: ["StockSpanner", "next", "next", "next", "next", "next", "next", "next", "next"], [[], [100], [60], [60], [75], [85] 출력: [null, 1, 1, 1, 2, 1, 4, 6] 설명: 우선 S = StockSpanner () 를 초기 화 한 다음 S. next (100) 가 호출 되 고 1, S. next (80) 가 호출 되 고 1, S. next (60) 가 호출 되 고 1 로 되 돌아 갑 니 다.S. next (70) 가 호출 되 고 2 로 되 돌아 갑 니 다. S. next (60) 가 호출 되 고 1 로 되 돌아 갑 니 다. S. next (75) 가 호출 되 고 4 로 되 돌아 갑 니 다. S. next (85) 가 호출 되 고 6 으로 되 돌아 갑 니 다.
주의 (예 를 들 어) S. next (75) 는 4 를 되 돌려 줍 니 다. 왜냐하면 오늘 의 마지막 4 개 가격 (오늘 의 가격 포함 75) 이 오늘 의 가격 보다 작 거나 같 기 때 문 입 니 다.
알림:
StockSpanner. next (int price) 를 호출 할 때 1 < = price < = 10 ^ 5 가 있 습 니 다.각 테스트 용례 는 최대 10000 회 StockSpanner. next 를 호출 할 수 있 습 니 다.모든 테스트 용례 에서 최대 15000 회 StockSpanner. next 를 호출 합 니 다.이 문제 의 총 시간 제한 이 50 퍼센트 감소 했다.
생각:
단조 로 운 스 택, 맵 캐 시 이전의 결 과 를 이용 합 니 다.
문제 풀이:
class StockSpanner {
HashMap<Integer, Integer> map;
Stack<Integer> s;
public StockSpanner() {
map = new HashMap<>();
s= new Stack<>();
}
public int next(int price) {
int result= 0;
if(s.empty()){
s.push(price);
result=1;
map.put(price,result);
return result;
}
if(!s.empty()&&price<s.peek()){
result=1;
s.push(price);
}else if(!s.empty()&&price>=s.peek()){
result=1;
while(!s.empty()&&price>=s.peek()){
int temp=s.pop();
int a=map.get(temp);
result+=a;
}
s.push(price);
}
map.put(price,result);
return result;
}
}
/**
* Your StockSpanner object will be instantiated and called as such:
* StockSpanner obj = new StockSpanner();
* int param_1 = obj.next(price);
*/