LeetCode75
334. Increasing Triplet Subsequence
Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.
Example 1:
Input: nums = [1,2,3,4,5] Output: true Explanation: Any triplet where i < j < k is valid.
Example 2:
Input: nums = [5,4,3,2,1] Output: false Explanation: No triplet exists.
Example 3:
Input: nums = [2,1,5,0,4,6] Output: true Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.
Constraints:
1 <= nums.length <= 5 * 105-231 <= nums[i] <= 231 - 1📌 یافتن سهتایی افزایشی در O(n)
هدف: بررسی کنیم که آیا در آرایهی nums سه عدد به ترتیب افزایشی (nums[i] < nums[j] < nums[k] با i < j < k) وجود دارد یا نه.
✅ روش بهینه:
first) و دومین کوچکترین (second) عددی که تاکنون دیدهایم را نگه میداریم.✅ چرا این روش O(n) است؟
چون فقط یک بار روی آرایه حرکت میکنیم و مقدار first و second را در هر مرحله بهروز میکنیم.
first و second را مقداردهی اولیه میکنیم (∞ یعنی مقدار بسیار بزرگ).first = کوچکترین مقدار دیدهشده تاکنون.second = دومین کوچکترین مقدار دیدهشده تاکنون.nums)num در nums:اگر num از first کوچکتر یا مساوی بود، مقدار first را بهروز کن (first = num).num از second کوچکتر یا مساوی بود، مقدار second را بهروز کن (second = num).num از second بزرگتر بود، یعنی یک triplet پیدا شده است → مقدار True را برگردان.tripletای پیدا نشد، False را برگردان.📌 پیادهسازی کد:
class Solution:
def increasingTriplet(self, nums):
# کوچکترین مقدار
first = float('inf')
# دومین کوچکترین مقدار
second = float('inf')
for num in nums:
# مقدار جدید از first کوچکتر است → first را آپدیت کن
first = num
# مقدار جدید بین first و second است → second را آپدیت کن
second = num
else:
# مقدار جدید بزرگتر از first و second است → سهتایی یافت شد
return True
# اگر کل آرایه را بررسی کردیم و پیدا نشد
return False
# علی برادر خدام خسروشاهی
✅ پیچیدگی زمانی: O(n) (چون فقط یک بار از چپ به راست حرکت میکنیم)
✅ پیچیدگی فضایی: O(1) (فقط دو متغیر first و second را نگه میداریم)
🚀 این روش O(n)، بهینهترین راه برای پیدا کردن یک سهتایی افزایشی در آرایه است.
✔️ نیازی به دو حلقه تو در تو (O(n²)) یا مرتبسازی (O(n log n)) ندارد.
✔️ فقط با دو مقدار حداقلی (first و second) کل آرایه را در یک دور پردازش میکنیم.
علی برادر خدام خسروشاهی
