Increasing Triplet Subsequence (M)
題目
Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.
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.
Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.
Example 1:
Input: [1,2,3,4,5]
Output: true
Example 2:
Input: [5,4,3,2,1]
Output: false
題意
判斷給定陣列中是否存在一組下標為i、j、k的數，滿足i<j<k且arr[i]<arr[j]<arr[k]，要求時間復雜度為\(O(N)\)且空間復雜度為\(O(1)\)，
思路
如果沒有空間復雜度的要求，比較容易想到的方法是再建兩個陣列leftMax和rightMin，leftMax[i]表示從首元素到i中最大的數，rightMin[j]表示從j到末元素中最小的數，如果存在leftMax[i]<arr[i]<rightMin[i]，說明存在滿足條件的三元組，
為了滿足\(O(1)\)的空間復雜度要求，可以這樣實作：設兩個變數small和mid，從左向右遍歷陣列，如果arr[i]<=small，更新small，否則如果arr[i]<=mid，更新mid，這樣當遍歷到下標為i的數時，small表示0-(i-1)中最小的數，mid表示0-(i-1)中第二小的數 (描述的是存在關系，具體的相對位置不一定正確)，只要arr[i]>mid，說明就能構成嚴格遞增的三元組，
代碼實作
Java
class Solution {
public boolean increasingTriplet(int[] nums) {
int small = Integer.MAX_VALUE, mid = Integer.MAX_VALUE;
for (int num : nums) {
if (num <= small) {
small = num;
} else if (num <= mid) {
mid = num;
} else {
return true;
}
}
return false;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/33841.html
標籤：其他
上一篇：0350. Intersection of Two Arrays II (E)
下一篇：單鏈表插入洗掉完整版