2 단 대기 열 문제 풀이
239. 슬라이딩 창 최대 값
소 객 링크 LeetCode 링크
방법 1: 폭력 법
이 문제 의 가장 직접적인 해법 은 모든 미끄럼 창 을 직접 옮 겨 다 니 며 각 창의 최대 치 를 찾 으 면 된다.모두 N - k + 1 개의 미끄럼 창 이 있 고 미끄럼 창 마다 k 개의 요소 가 있 기 때문에 시간 복잡 도 는 O (Nk) 로 표현 이 좋 지 않 습 니 다.
방법 2: 양 끝 대기 열
여 기 는 양 방향 링크 로 이 루어 진 링크 드 리스트 를 쌍 단 대기 열 로 사용 합 니 다.알고리즘
전체 배열 을 옮 겨 다 니 며..
4. 567917. 현재 요소 의 색인 을 쌍 단 대기 열 에 추가 하고 추가 하기 전에 먼저 쌍 단 대기 열 을 정리 합 니 다.
현재 양 끝 대기 열 을 옮 겨 다 니 고 있 습 니 다
4. 567917. 현재 요소 보다 작은 모든 요 소 를 제거 합 니 다. 그들 은 가장 큰 것 이 될 수 없습니다. 양 끝 팀 의 선두 부터 팀 의 끝 까지 큰 순서 에서 작은 순서 로 배열 하도록 보장 합 니 다. 그러면 팀 의 첫 번 째 가 현재 창 에서 가장 큰 것 임 을 보장 합 니 다
4. 567917. 팀 의 첫 번 째 색인 이 창 을 넘 으 면 첫 번 째 색인 을 삭제 합 니 다
출력 배열 에 첫 번 째 요 소 를 추가 합 니 다
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums == null || nums.length == 0) return new int[0];
LinkedList<Integer> qmax = new LinkedList<>();
int[] result = new int[nums.length - k + 1];
int index = 0;
for(int i = 0; i < nums.length; i++) {
// ，
while(!qmax.isEmpty() && nums[i] >= nums[qmax.peekLast()]) {
qmax.pollLast();
}
//
qmax.addLast(i);
// ，
if(qmax.peekFirst() == i - k) {
qmax.pollFirst();
}
// ，
if(i >= k - 1) {
result[index++] = nums[qmax.peekFirst()];
}
}
return result;
}
복잡 도
4. 567917. 시간 복잡 도: O (N), 각 요 소 는 두 번 처리 되 고 색인 은 쌍 단 대기 열 에 추가 되 며 쌍 단 대기 열 에 의 해 삭 제 됩 니 다
4. 567917. 공간 복잡 도: O (N), 출력 배열 은 O (N - k + 1) 를 사 용 했 고 양 끝 대기 열 은 O (k) 를 사용 했다
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
