leetcode503. Next Greater Element II

1783 단어 leetcode자바stack
제목 요구
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;
    }

좋은 웹페이지 즐겨찾기