※ 이 포스트는 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
유럽 여행 2주간 대학 친구와 유럽여행을 다녀왔다. 런던 출장외에 유럽 여행은 완전 처음이었는데, 좋았던 점이…
Layoff 이번 주에 또 한차례 Layoff가 있었다. 작년 1월 대규모 Layoff 이후 1년만의 일이다. 새벽…
2023 회고 큰 성공을 만든 건 없지만, 작년에 달성한 것들을 모아보자면 일단 잘리지 않고 해고를…
영주권 매일 아침 USPS 이메일과 USCIS 앱을 열어보면서 기다리던 영주권이 드디어 발급되었다. 오늘 드디어 새로…
TL;DR 이 일기는 OKR 설정의 어려움, 효과적인 마케팅 전략의 필요성, 가족 중심의 삶과 이민자로서의 경력…
TL;DR 미국 생활에 찾아온 작은 변화와 가족과의 여행 소소한 행복, 그리고 AI 기술의 급속한 발전…
This website uses cookies.