給定一個整數數組nums，如果存在索引三元組(i, j, k) 且i
你能實作以 O(n) 時間複雜度和 O(1) 空間複雜度運作的解決方案嗎？
為了有效地解決這個問題，我們需要追蹤迄今為止遇到的最小和第二小的值。如果我們找到大於第二小的值的第三個值，那麼我們就找到了遞增三元組。
暴力解決方案涉及檢查所有可能的三元組，看看是否存在滿足條件 i
function increasingTripletBruteForce(nums: number[]): boolean {
const n = nums.length;
for (let i = 0; i < n - 2; i++) {
for (let j = i + 1; j < n - 1; j++) {
for (let k = j + 1; k < n; k++) {
if (nums[i] < nums[j] && nums[j] < nums[k]) {
return true;
}
}
}
}
return false;
}
暴力解決方案效率不高，不適合大輸入。
最佳化的解決方案涉及迭代數組，同時維護兩個變量，第一和第二，它們代表迄今為止遇到的最小和第二小的值。如果我們找到大於秒的值，則傳回 true。
function increasingTriplet(nums: number[]): boolean {
let first = Infinity;
let second = Infinity;
for (let num of nums) {
if (num <= first) {
first = num; // smallest value
} else if (num <= second) {
second = num; // second smallest value
} else {
return true; // found a value greater than second smallest, thus an increasing triplet exists
}
}
return false;
}
console.log(increasingTripletBruteForce([1,2,3,4,5])); // true console.log(increasingTripletBruteForce([5,4,3,2,1])); // false console.log(increasingTripletBruteForce([2,1,5,0,4,6])); // true console.log(increasingTripletBruteForce([1,1,1,1,1])); // false console.log(increasingTripletBruteForce([1,2])); // false console.log(increasingTripletBruteForce([1,2,3])); // true console.log(increasingTripletBruteForce([1,5,0,4,1,3])); // true console.log(increasingTriplet([1,2,3,4,5])); // true console.log(increasingTriplet([5,4,3,2,1])); // false console.log(increasingTriplet([2,1,5,0,4,6])); // true console.log(increasingTriplet([1,1,1,1,1])); // false console.log(increasingTriplet([1,2])); // false console.log(increasingTriplet([1,2,3])); // true console.log(increasingTriplet([1,5,0,4,1,3])); // true
子數組問題：
雙指針技術：
就地演算法：
透過練習這些問題和策略，您可以提高解決問題的能力，並為各種編碼挑戰做好更好的準備。
以上是Typescript 編碼編年史：增加三元組子序列的詳細內容。更多資訊請關注PHP中文網其他相關文章！
