leetcode503. Next Greater Element II
Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn't exist, output -1 for this number.
Example 1:
Input: [1,2,1]Output: [2,-1,2]Explanation: The first 1's next greater number is 2; The number 2 can't find next greater number; The second 1's next greater number needs to search circularly, which is also 2.
Note:The length of given array won't exceed 10000.
현재 순환 배열, 즉 배열 의 첫 번 째 요 소 는 배열 의 마지막 요소 의 다음 요소 라 고 가정 합 니 다.현재 새로운 배열 을 생 성 해 야 합 니 다. 이 새로운 배열 의 모든 요 소 는 원래 배열 에서 첫 번 째 로 아래 표 시 된 요소 보다 큰 값 을 표시 합 니 다.
아이디어 와 코드
이 배열 이 순환 배열 이 아니라면 스 택 의 한 바퀴 를 통 해 모든 요소 의 다음 더 큰 요 소 를 찾 을 수 있 습 니 다.찾 아 낸 방법 은 스 택 꼭대기 보다 큰 요 소 를 만나면 스 택 에 있 는 요 소 를 종료 하 는 것 입 니 다. 현재 요 소 는 스 택 꼭대기 요소 의 다음 더 큰 요소 이기 때 문 입 니 다.
그러나 이 배열 은 순환 배열 이기 때문에 한 번 더 배열 을 옮 겨 다 니 기만 하면 됩 니 다. 이 라 운 드 는 요 소 를 스 택 에 넣 을 필요 가 없습니다. 현재 요소 보다 작은 스 택 꼭대기 요 소 를 계속 꺼 내 면 됩 니 다.배열 의 최대 요 소 는 이 알고리즘 에서 영원히 팝 업 되 지 않 기 때문에 결과 집중 의 기본 값 을 - 1 로 설정 해 야 합 니 다.
public int[] nextGreaterElements(int[] nums) {
int n = nums.length, next[] = new int[n];
Arrays.fill(next, -1);
Stack stack = new Stack<>(); // index stack
for (int i = 0; i < n * 2; i++) {
int num = nums[i % n];
while (!stack.isEmpty() && nums[stack.peek()] < num)
next[stack.pop()] = num;
if (i < n) stack.push(i);
}
return next;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.