关于LeetCode递增三元子序列Accepted解法的逻辑疑问
递增三元子序列O(n)解法正确性解惑
我在研究递增三元子序列问题的O(n)复杂度解法时,发现许多人使用的如下代码被LeetCode判定为Accepted:
class Solution: def increasingTriplet(self, nums: List[int]) -> bool: if len(nums) < 3: return False i = float('inf') j = float('inf') for num in nums: if num <= i: i = num elif num <= j: j = num else: return True return False
我对这个解法的正确性存疑——该解法似乎未考虑递增三元组的索引要求:三元组的索引必须满足i<j<k且nums[i]<nums[j]<nums[k],但看起来违反了索引递增规则。
以测试用例 nums = [3, 8, 1, 5, 2, 0, 10, 12] 为例,代码返回True,但按代码逻辑似乎会对应到值为0、2、10的元素,它们的索引是5、4、6,不符合i<j<k的要求。不过我清楚这个测试用例中存在合法三元组,比如索引0、1、6对应的3、8、10。
我是否遗漏了问题的核心要点?
内容的提问来源于stack exchange,提问作者Md Mohaimenuzzaman
相关产品推荐
相关产品推荐

