Monotonic Stack 도입을 통한 시간 복잡도 O(N*M)에서 O(N+M)으로 최적화

Context

nums1의 각 요소에 대해 nums2 내 우측의 첫 번째 큰 값을 찾는 문제 상황. Brute Force 방식의 중복 스캔으로 인한 O(N*M) 시간 복잡도 발생 및 대규모 데이터셋 처리 시의 성능 저하가 한계점으로 파악됨.

Technical Solution

• nums2를 우측에서 좌측으로 역방향 순회하여 Next Greater Element를 사전 계산하는 구조 설계
• Monotonic Decreasing Stack을 활용해 현재 요소보다 작은 값을 제거함으로써 유효한 후보군만 유지하는 로직 구현
• Stack Top을 즉각적인 정답으로 활용하여 불필요한 배열 탐색 과정을 제거한 설계
• 사전 계산된 결과를 HashMap에 저장하여 nums1의 쿼리를 O(1) 시간 복잡도로 처리하는 매핑 전략 채택
• 모든 요소가 Stack에 단 한 번 진입하고 유출되는 구조를 통한 연산 효율성 극대화