LeetCode - 503. 다음 더 큰 요소 II (Next Greater Element II) [중간] - 분석 및 코드 (Java)
7530 단어 데이터 구조 와 알고리즘LeetCodeJava해제
순환 배열 (마지막 요소 의 다음 요 소 는 배열 의 첫 번 째 요소) 을 지정 하고 모든 요소 의 다음 요 소 를 출력 합 니 다.숫자 x 의 다음 더 큰 요 소 는 배열 에 따라 순 서 를 옮 겨 다 니 는 것 입 니 다. 이 숫자 뒤의 첫 번 째 는 그것 보다 더 큰 숫자 입 니 다. 이것 은 다음 더 큰 숫자 를 순환 적 으로 검색 해 야 한 다 는 것 을 의미 합 니 다.존재 하지 않 으 면 출력 - 1.
예시 1:
: [1,2,1]
: [2,-1,2]
: 1 2；
2 ；
1 ， 2。
: 10000。
출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/next-greater-element-ii 저작권 은 인터넷 에 귀속 된다.상업 전 재 는 정부 에 연락 하여 권한 을 부여 해 주 십시오. 비 상업 전 재 는 출처 를 밝 혀 주 십시오.
2. 분석 및 코드
1. 단조 창고
(1) 사고방식
단조 로 운 스 택 을 설계 하여 아래 에서 위로 큰 것 부터 작은 것 까지 일치 하지 않 는 요 소 를 저장 합 니 다.새 요소 가 스 택 꼭대기 보다 크 면 새 요소 의 크기 는 스 택 꼭대기 요소 의 다음 더 큰 요소 입 니 다. 스 택 이 비어 있 거나 새 요소 가 스 택 꼭대기 보다 작 을 때 까지 새 요 소 를 스 택 에 추가 합 니 다.배열 이 순환 할 수 있 기 때문에 두 번 째 로 옮 겨 다 닐 수 있 고 각 요소 가 선행 위치 에 있 는 다음 더 큰 요 소 를 찾 을 수 있 도록 합 니 다.두 번 옮 겨 다 니 면 스 택 에 남 은 요 소 는 원래 배열 의 최대 값 입 니 다.주어진 배열 에 따라 요소 의 색인 에서 요소 의 크기 를 직접 얻 을 수 있 기 때문에 스 택 에 색인 을 저장 하고 처리 하면 됩 니 다.
(2) 코드
class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
if (n == 0)
return ans;
Arrays.fill(ans, -1);
Stack<Integer> sta = new Stack<>();// ，
for (int i = 0; i < n; i++) {
while (!sta.empty() && nums[sta.peek()] < nums[i])
ans[sta.pop()] = nums[i];
sta.add(i);
}
for (int i = 0; i < n; i++) {
while (!sta.empty() && nums[sta.peek()] < nums[i])
ans[sta.pop()] = nums[i];
}
return ans;
}
}
(3) 결과
실행 시: 8ms, 모든 자바 제출 에서 85.75% 의 사용 자 를 격파 하 였 습 니 다.메모리 소모: 40.2 MB, 모든 자바 제출 에서 49.36% 의 사용 자 를 격파 하 였 습 니 다.
기타
잠시 없다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[JAVA] 배열 회전 출력요소 가 출력 을 시작 하 는 위치 에 주의 하 십시오. 모두 몇 라운드 의 수출 이 있 습 니까? n/2 + 1 매 라 운 드 는 상, 우, 하, 좌 로 나 뉜 다. 각 방향의 시작 위치 와 좌표 의 관 계 를 구...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
