【Leetcode】496. Next Greater Element I

제목 주소:
https://leetcode.com/problems/next-greater-element-i/
제목 의 대 의 는 두 배열 의 nums 1 과 nums 2 를 정 하고 전 자 는 후자 의 부분 집합 이다.모든 nums 1 의 요소 에 대해 nums 2 의 오른쪽 숫자 에서 첫 번 째 로 큰 요 소 를 구하 고 존재 하지 않 으 면 답 을 - 1 로 규정 합 니 다.예 를 들 어 n u m s 1 = [4, 1, 2], n u m s 2 = [1, 3, 4, 2] nums 1 = [4, 1, 2], nums 2 = [1, 3, 4, 2] nums 1 = [4, 1, 2], nums 2 = [1, 3, 4, 2] 이면 정 답 은 [- 1, 3, - 1] [- 1, 3, - 1] [- 1, 3, - 1] [- 1, 3, - 1] 이다.이 문 제 는 전형 적 인 단조 로 운 스 택 의 응용 이다.기본 적 인 사 고 는 nums 2 의 요 소 를 순서대로 push 를 한 스 택 에 넣 고 스 택 요소 의 단조 로 운 체감 성 을 유지 하 는 것 입 니 다.즉, 스 택 꼭대기 요소 가 다음 push 요소 보다 작 다 는 것 을 발견 하면 이 스 택 꼭대기 요소 에 대응 하 는 다음 최대 요 소 는 push 를 원 하 는 이 요소 라 고 인정 할 수 있 습 니 다. 그래서 스 택 꼭대기 pop 을 스 택 이 비어 있 거나 스 택 꼭대기 가 이 요소 보다 클 때 까지 합 니 다.위의 예 를 들 어 push 1 을 스 택 에 들 어가 고 push 3 을 스 택 에 들 어 가 려 고 했 습 니 다. 스 택 꼭대기 요소 1 이 3 보다 작 기 때문에 1 의 다음 가장 큰 요 소 는 3 입 니 다. 그러면 1 pop 입 니 다. 이때 스 택 이 비어 있 고 3 push 를 발 견 했 습 니 다. 이 어 4 대 3 대 를 발 견 했 습 니 다. pop 3 push 4 는 다음 에 push 2 가 단조 성 을 위반 하지 않 았 기 때문에 push 2 를 다시 발 견 했 습 니 다.팝 요 소 를 사용 할 때마다 해시 맵 으로 이 요소 의 다음 최대 요 소 를 기록 하고 마지막 으로 정리 합 니 다.코드 는 다음 과 같 습 니 다:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length];
        //   
        if (nums2 == null || nums2.length == 0) {
            Arrays.fill(res, -1);
            return res;
        }
        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> map = new HashMap<>();
   
        for (int i = 0; i < nums2.length; i++) {
        	//         push   ，  map    pop 
            while (!stack.isEmpty() && stack.peek() < nums2[i]) {
                map.put(stack.pop(), nums2[i]);
            }
            stack.push(nums2[i]);
        }
    
        for (int i = 0; i < nums1.length; i++) {
            res[i] = map.getOrDefault(nums1[i], -1);
        }
        
        return res;
    }
}

시간 공간의 복잡 도 는 모두 O (n u m s 2. l e n g t h) O (nums 2. length) O (nums 2. length) 이다.
알고리즘 복잡 도 증명 map.put(stack.pop(), nums2[i]); 은 모두 O (n u m s 2. l e n g t h) O (nums 2. length) O (nums 2. length) 회 를 실 행 했 습 니 다.
알고리즘 정확성 증명: 첫 번 째 순환 에 대해 먼저 하나의 결론 을 증명 합 니 다. 순환 i i 가 끝 날 때 1. 스 택 이 비어 있 지 않 고 요소 가 엄격 하고 단조 로 우 며 2. map 에 n u m s 2 [0,..., i - 1] nums 2 [0,..., i - 1] nums 2 [0,..., i - 1] 에 있 는 next greater element 는 n u m s 2 [1,.., i] nums 2 [1, i] nums 2 [1,...그 숫자 와 next greater element 으로 구 성 된 pair, map 의 모든 key 가 스 택 에서 나 왔 습 니 다.
수학 귀납법: i = 0 i = 0 i = 0 시 순환 이 끝 날 때 n u m s [0] nums [0] nums [0] nums [0] 가 스 택 에 들 어가 면 map 는 이때 비어 있 고 두 가지 성질 이 모두 만족 합 니 다.i = k i = k i = k i = k 일 때 결론 이 성립 된다 고 가정 하면 i = k + 1 i = k + 1 i = k + 1 일 때 순환 이 끝 날 때 n u m s [k + 1] nums [k + 1] nums [k + 1] nums [k + 1] 보다 작은 요소 가 모두 스 택 에 나 왔 기 때문에 귀납 적 가설 에 의 해 n u m s [k + 1] nums [k + 1] nums [k + 1] 가 스 택 에 들 어가 기 전에 스 택 이 비어 있 거나 단조 로 운 것 이기 때문에 스 택 에 들 어간 후에 비 어 있 거나 단조 로 운 것 이 모두 성립 된다.성질 2 에 대해 i = k + 1 i = k + 1 i = k + 1 의 순환 이 시 작 될 때 스 택 이 비어 있 으 면 이 순환 이 끝 날 때 스 택 에 하나의 요소 만 있 고 map 는 새로운 put 하나의 entry 가 없 으 며 성질 2 만족 합 니 다.스 택 이 비어 있 지 않 으 면 귀납 적 가설 에서 map 의 성질 로 스 택 안의 모든 요소 의 next greater element 는 n u m s 2 [0,..., k] nums 2 [0,..., k] nums 2 [0,..., k] 에 있 지 않 습 니 다. 이때 n u m s [k + 1] nums [k + 1] nums [k + 1] nums [k + 1] 가 스 택 꼭대기 요소 보다 크 면 스 택 꼭대기 요소 의 next greater element 는 반드시 n u m s [k + 1] nums [k + 1] nums [k + 1] 입 니 다. 그래서 스 택 꼭대기 요소 가 스 택 에서 나 옵 니 다.또한 map 에 이 요소 와 그의 next greater element n u m s [k + 1] nums [k + 1] nums [k + 1] nums [k + 1] 를 넣 고 이렇게 조작 합 니 다. 창고 꼭대기 요소 가 n u m s [k + 1] nums [k + 1] nums [k + 1] (nums 2 요소 가 서로 다 르 기 때문에 여 기 는 같 지 않 고 크 기 때 문 입 니 다). 이때 창고 안의 요소 의 next greater element 는 n u m s 2 [0.., k + 1] nums 2 에 없습니다.[0,..., k + 1] nums 2 [0,..., k + 1] 에서 map 는 모든 next greater element 를 n u m s [k + 1] nums [k + 1] nums [k + 1] nums [k + 1] 의 pair 로 귀납 적 가설 과 결합 하여 성질 2 가 성립 되 었 다.
알고리즘 의 정확성 은 i = n i = n i = n 의 순환 이 끝 날 때의 성질 2 에서 나온다.