LeetCode 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points 자바 문제 풀이

문제 설명

• 문제: LeetCode 2058. Nodes Between Critical Points
• 설명: 주어진 단일 연결 리스트에서 local maxima(큰 값) 또는 local minima(작은 값)의 노드 사이의 최소 거리와 최대 거리를 찾아야 합니다.
  • local maxima는 양 옆의 노드의 값보다 큰 값을 말합니다. ex) 3-9-6
  • local minima는 양 옆의 노드의 값보다 작은 값을 말합니다. ex) 6-1-7

접근 방식

• 아이디어:
  • 링크드리스트에서 각 노드의 값이 local maxima혹은 local minima인지 확인하여 이 값을 미리 저장해둡니다.
  • 저장된 값을 비교하여 최소 거리와 최대 거리를 찾습니다.
• 알고리즘:
  1. 각 노드의 값이 local maxima혹은 local minima인지 확인하기위해 시작노드, 그다음 노드, 그 다음다음 노드를 확인합니다.
  2. 위의 조건을 위해 링크드리스트의 마지막 두 노드는 빼고 순회 합니다.
  3. 필요한 값은 노드의 값이 아니라 인덱스이므로, 이 인덱스 역시 따로 계산합니다. 순회 한번당 값을 1 추가합니다.
  4. 리스트에 저장된 인덱스 값을 이용하여 최소 거리와 최대 거리를 구합니다.
  5. 순회하며 값을 넣었으므로, 이미 정렬된 리스트입니다.
  6. 최대값=마지막값+첫번째 값
  7. 최소값은 다시 리스트를 순회하며, 각 거리를 계산후, 비교하여 구합니다.

코드

class Solution {
    public int[] nodesBetweenCriticalPoints(ListNode head) {
        ListNode temp = head;
        List<Integer> list = new ArrayList<>();
        int index = 1;
        int[] result = {-1, -1};

        while (temp != null && temp.next != null && temp.next.next != null) {
            ListNode prev = temp;
            ListNode curr = temp.next;
            ListNode next = temp.next.next;

            if ((curr.val > prev.val && curr.val > next.val) ||
                (curr.val < prev.val && curr.val < next.val)) {
                list.add(index);
            }

            temp = temp.next;
            index++;
        }

        int n = list.size();
        if (n < 2) {
            return result;
        }

        int minDistance = Integer.MAX_VALUE;

        for (int i = 1; i < n; i++) {
            minDistance = Math.min(minDistance, list.get(i) - list.get(i - 1));
        }

        int maxDistance = list.get(n - 1) - list.get(0);

        result[0] = minDistance;
        result[1] = maxDistance;

        return result;
    }
}

결론

• 시간 복잡도: 연결 리스트를 한 번 순회하면서 임계점을 찾는 데 O(n)의 시간이 필요합니다. 임계점 사이의 거리를 계산하는 과정도 O(n)입니다. 따라서 전체 알고리즘의 시간 복잡도는 O(n)입니다.
• 공간 복잡도: 추가적인 공간을 사용하지 않으므로 O(1)입니다.