NextGreaterElementII

Published at 2022-04-14

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        stack = []
        res = [-1] * len(nums)
        
        def loop():
            for i in range(len(nums)):
                while stack and nums[stack[-1]] < nums[i]:  # stack에는 이전 인덱스 저장되어 있음. 걔가 [i]보다 작다는건?
                    res[stack.pop()] = nums[i]  # stack에 있는 [i]보다 작은 모든 이전 인덱스에 현재 숫자 기록하기
                stack.append(i)
            return
        
        # 배열은 순환된다는 설정이니 두 번 실행
        loop()
        loop()
        
        return res
    
    
    # i 이후로 가장 먼저 만나는 가장 큰 수 찾는거니까
    # 뒤부터 돌면서 i보다 클 경우 stack 에 저장해나가면됨
    #   ㄴ 근데 이건 solution에 있는 거꾸로 도는 방법이고 내 풀이는 정방향
    
    # [3,8,4,1,2] 일때 맨 처음에 stack에 2 저장
    # 다음인 1은 스택에있는 2보다 작으니 정답에 기록함
    # 그 다음은 4인데 스택에 쌓여있는 2와 1 모두 4보다 작음.
    # 그럼 스택을 모두 제거하고 4를 저장함. 왜냐면 1이랑 2가 4보다 작아서
    # 이 앞에있는 숫자의 중 가장 가까운 큰 수는 어차피 4일테니까.
    # 8을 만났을때도 동일한 이유로 스택의 4를 팝해줌
    # 3을 만났을때는 스택의 8을 정답에 기록.
    
    # 여기서 루프를 한 번 더 돈다.
    # 스택에는 현재 8, 3이 쌓인 상태
    # 다시 마지막의 2를 만났을 때 스택의 젤 위인 3이 2보다 크다.
    # 그러므로 2의 정답에 3을 기록 & 스택에 2를 쌓음
    # 이 과정을 반복한다.
    
    # 여기서 바로다음큰수를 찾아서 정답에 기록을 할 경우 왜 스택을 안비우냐?
    # 이 예시에선 숫자간 차이가 별로 없지만
    # [i]의 숫자가 스택 최상단 숫자보다 클수도, 스택최상~차상 사이일수도, 차상보다 작을수도.... 의 경우의 수가 있기 때문에
    # 스택에 일단 다 저장해둔다음 [i], [i-1], [i-2] , ... 으로 비교하는것
    
    # 하지만 스택의 값들이 [i]보다 큰게 하나도 없었고 스택은 모두 비워졌으면
    # 이 앞에 있는 숫자들은 무조건 가장큰다음숫자가 [i]일테니 스택에 얘만 저장