Increasing Triplet Subsequence
Formally the function should:
Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Your algorithm should run in O(n) time complexity and O(1) space complexity.
Examples:
Given [1, 2, 3, 4, 5],
return true.
Given [5, 4, 3, 2, 1],
return false.
정렬 되 지 않 은 배열 에서 세 개의 요소 가 존재 하 는 지 확인 하고 arr [i] < arr [j] < arr [k], (0 ≤ i < j < k ≤ n - 1) 를 만족 시 킵 니 다.
선형 시간 에 찾 아야 하고 공간의 복잡 도 는 O (1) 이다.우 리 는 두 개의 변 수 를 min 1, min 2 로 유지 하고 min 1 < min 2, 그리고 min 1 은 min 2 의 왼쪽 에 있 기 때문에 우 리 는 하나의 요소 가 min 2 보다 크 면 true 로 돌아 갈 수 있 습 니 다.이렇게 시간 복잡 도 는 O (n) 이 고 공간 복잡 도 는 O (1) 이다.코드 는 다음 과 같 습 니 다:
public class Solution {
public boolean increasingTriplet(int[] nums) {
if(nums == null || nums.length < 3) return false;
int min1 = Integer.MAX_VALUE;
int min2 = Integer.MAX_VALUE;
for(int i : nums) {
if(i <= min1) min1 = i;
else if(i <= min2) min2 = i;
else if(i > min2) return true;
}
return false;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Is Eclipse IDE dying?In 2014 the Eclipse IDE is the leading development environment for Java with a market share of approximately 65%. but ac...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
