[코테연습] 3105. Longest Strictly Increasing or Strictly Decreasing Subarray

https://leetcode.com/problems/longest-strictly-increasing-or-strictly-decreasing-subarray/description/?envType=daily-question&envId=2025-02-03

 

 

문제 타입

• 투 포인터 (Two Pointers)
• 슬라이딩 윈도우 (Sliding Window)
• 배열 (Array)

---

🔹 문제 분석

• 주어진 배열에서 연속한 부분 배열(subarray) 중에서
  1. **엄격하게 증가(strictly increasing)**하거나
  2. **엄격하게 감소(strictly decreasing)**하는
     가장 긴 부분 배열의 길이를 찾는 문제.
• 같은 값이 연속되면 증가/감소가 끊어지므로 부분 배열을 새로 시작해야 함.
• 부분 배열은 연속된 요소들로 이루어져야 하며, 배열을 순회하면서 최대 길이를 찾아야 함.

---

🔹 문제 풀이 (Java 코드 참고)

✅ 투 포인터 / 슬라이딩 윈도우 활용

1. 두 개의 변수(incLen, decLen)를 사용하여 증가/감소 길이 추적
   • incLen: 현재 증가하는 부분 배열 길이
   • decLen: 현재 감소하는 부분 배열 길이
   • maxLen: 지금까지 찾은 가장 긴 증가 또는 감소 부분 배열 길이
2. 배열을 순회하며 이전 값과 현재 값을 비교
   • nums[i] > nums[i-1] → incLen += 1, decLen = 1 (증가하는 경우, 감소 길이 초기화)
   • nums[i] < nums[i-1] → decLen += 1, incLen = 1 (감소하는 경우, 증가 길이 초기화)
   • nums[i] == nums[i-1] → incLen = decLen = 1 (같은 값이면 초기화)
3. 각 단계에서 maxLen을 갱신하여 최댓값을 저장.
4. 배열을 한 번만 순회하면서 최적화된 방식으로 결과 도출.

✅ 시간 복잡도

• O(N): 배열을 한 번만 순회하면서 최대 길이를 갱신하므로 효율적.

✅ 공간 복잡도

• O(1): 추가 공간 없이 변수만 사용하여 해결.

 

 

class Solution {
    public int longestMonotonicSubarray(int[] nums) {
        int n = nums.length;
        if (n == 1) return 1;

        int maxLen = 1;
        int incLen = 1, decLen = 1;

        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1]) {
                incLen++;
                decLen = 1; // 증가하는 경우, 감소 길이는 초기화
            } else if (nums[i] < nums[i - 1]) {
                decLen++;
                incLen = 1; // 감소하는 경우, 증가 길이는 초기화
            } else {
                incLen = decLen = 1; // 같은 값이면 초기화
            }
            maxLen = Math.max(maxLen, Math.max(incLen, decLen));
        }

        return maxLen;
    }
}