Re: [閒聊] 每日LeetCode
334. Increasing Triplet Subsequence
給予一個陣列，判斷是否存在一個嚴格遞增的子序列。
Example 1:
Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any triplet where i < j < k is valid.
思路：
1.維護兩個整數分別表示序列裡最小值min和第二大的值mid，前者初始化為陣列第一個
數字，後者初始化為一個極大值。
2.遍歷陣列：
> 若數字n比最小值min還小，更新min為更小的值
> 若數字n比最小值min還大且比mid小，則更新mid為較小的值
> 若數字n比mid還大表示[min, mid, n] 組成了嚴格遞增序列，返回true。
3.由於產生新的mid前保證了一定有一個數小於mid，因此保證了即使min變成其他更小的
數了，只要存在一個大於mid的值，仍可組成遞增序列。
4 5 1 9
min = 4, mid = 5
4 5 1 9
min = 1, mid = 5
4 5 1 9
min = 1, mid = 5
[1, 5, 9] 雖然不是一個序列（沒照順序），但是因為我們更新mid之前都會檢查是否
比min大（新的mid一定比舊的min還大），所以可以他可以被還原成舊的min，1 ==> 4
[4, 5, 9]。
4.若遍歷完陣列都找不到比mid還大的n，返回false。
JavaCode：
class Solution {
public boolean increasingTriplet(int[] nums) {
if (nums.length < 3) return false;
int min = nums[0], mid = Integer.MAX_VALUE;
for (int i = 1; i < nums.length; i++) {
if (nums[i] < min)
min = nums[i];
else if (nums[i] > mid)
return true;
else if (nums[i] > min && nums[i] < mid)
mid = nums[i];
}
return false;
}
}
這題(O^2)就會TLE了...好嚴格
--
https://i.imgur.com/PIoxddO.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.6.111 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1665458481.A.7B3.html
※ 編輯: Rushia (36.231.6.111 臺灣), 10/11/2022 11:21:45
推
10/11 11:32,
1年前
, 1F
10/11 11:32, 1F
推
10/11 11:35,
1年前
, 2F
10/11 11:35, 2F
討論串 (同標題文章)
完整討論串 (本文為第 42 之 719 篇)：
閒聊
1
3