Open seungriyou opened 5 months ago
https://leetcode.com/problems/next-greater-element-ii/ similar to #90
각 원소마다 next (strictly) greater number를 찾아야 하므로 monotonic stack을 이용하여 O(n^2) brute-force 방식을 O(n)으로 개선할 수 있다.
O(n^2)
O(n)
monotonic stack은 non-increasing 형태로 구성한다. stack에 저장해둔 index에 해당하는 값보다 strictly greater 한 값을 찾을 때마다 res 값을 업데이트 해주어야 하므로!
res
circular array이므로 pass를 두 번 반복하면 된다! 이때, nums list 자체를 두배 늘리는 것보다, i index 값을 두 번 순회하는 편이 space 측면에서 낫다.
nums
i
Approach
각 원소마다 next (strictly) greater number를 찾아야 하므로 monotonic stack을 이용하여
O(n^2)
brute-force 방식을O(n)
으로 개선할 수 있다.circular array이므로 pass를 두 번 반복하면 된다! 이때,
nums
list 자체를 두배 늘리는 것보다,i
index 값을 두 번 순회하는 편이 space 측면에서 낫다.Complexity
O(n)
(2-pass 이지만 어쨌거나...)O(n)