[LeetCode / Medium] 334. Increasing Triplet Subsequence (Java)

💬 Info

• 난이도 : Medium
• 문제 링크 : https://leetcode.com/classic/problems/increasing-triplet-subsequence/description/
• 풀이 링크 : LeetCode/Medium/Increasing Triplet Subsequence.java

Problem

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

Example

예시 1

• Input: nums = [1,2,3,4,5]
• Output: true
• Explanation: Any triplet where i < j < k is valid.

예시 2

• Input: nums = [5,4,3,2,1]
• Output: false
• Explanation: No triplet exists.

예시 3

• Input: nums = [2,1,5,0,4,6]
• Output: true
• Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

Constraints

• 1 <= nums.length <= $5 * 10^5$
  = $-2^{31}$ <= nums[i] <= $2^{31}$ - 1

문제 이해

• 세 개의 수가 증가하는 부분 수열을 찾는 문제
  
  
  
  

알고리즘

풀이 시간 : 25분

• small : 가장 작은 값, big : 두 번째로 작은 값
• 배열 순회
  • 현재 숫자가 small보다 작거나 같으면 -> small이 현재 숫자
  • 현재 숫자가 big보다 작거나 같으면 -> big이 현재 숫자]
  • 현재 숫자가 big보다 크면 -> true
  • 조건에 맞는 증가하는 세 숫자가 없으면 -> false

class Solution {
  public boolean increasingTriplet(int[] nums) {
    int small = Integer.MAX_VALUE;
    int big = Integer.MAX_VALUE;
    
    for (int i = 0; i < nums.length; i++) {
      int num = nums[i];
      
      if (num <= small) {
        small = num;
      }
      if (num > small && num <= big) {
        big = num;
      }
      if (num > big) {
        return true;
      }
    }
    
    return false;
  }
}

결과