※ 이 포스트는 LeetCode 코딩 인터뷰 문제인 Increasing Triplet Subsequence의 해설을 담고 있습니다.
본 풀이는 Optimal하지 않을 수 있으며, LeetCode에서의 Submission 통과만을 보장합니다.
문제 출처 : https://leetcode.com/problems/increasing-triplet-subsequence/
카테고리 : DP(?), Greedy(?)
난이도 : 쉬움
어떤 정수 리스트 A가 주어졌을 때, i < j < k이고, A[i] < A[j] < A[k]인 (i, j, k)가 존재하는지를 리턴하여라
Simple – O(N)의 방법
배열 Min, Max를 정의한다.
Min[i]는 인덱스 A[0] ~ A[i]의 수 중에서 가장 작은 값을 저장한다.
Max[i]는 A[i] ~ A[size – 1] 중에서 가장 큰 값을 저장한다.
A[i]에 대해 A[i]와 Min[i]를 비교해서 A[i] > Min[i]이면, i 이전에 A[i] > A[j]인 j가 있다는 말이다.
같은 원리로 A[i]와 Max[j]를 비교해서 A[i] < Max[i]이면, i 이후에 A[i] < A[j]인 j가 있다는 말이다.
따라서 모든 i에 대해 Min[i] < A[i] < Max[i]인 i가 존재하면 True를 리턴하고, 아니면 False를 리턴하면 된다.
class Solution(object):
def increasingTriplet(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
# Return False on minimum size exception
if len(nums) < 3:
return False
# Init Size
size = len(nums)
Min, Max = [0] * size, [0] * size
# Init Min, Max array
Min[0] = nums[0]
for i in range(1, size):
Min[i] = min(nums[i], Min[i - 1])
Max[size - 1] = nums[size - 1]
for i in reversed(range(len(nums) - 1)):
Max[i] = max(nums[i], Max[i + 1])
# Compare nums[i] with min before i and max after i
for i in range(1, size - 1):
if Min[i] < nums[i] and nums[i] < Max[i]:
return True
return False
코딩 인터뷰 – Increasing Triplet Subsequence
Planning A well-structured plan has the following characteristics: First, the ultimate vision you aim to…
English The most common problem for English learners like myself is that we often use…
This website uses cookies.