提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

菜鸟的每日力扣系列——用贪心简化“最长上升子序列”问题

2023-02-18 16:23:57 时间

力扣334. 递增的三元子序列

如何在只做一次遍历就得到结果呢？因为结果只有三个元素，而且是按列表下标序递增变大，那么我的思路是用一个变量去存一次遍历中列表的最小值，如果遇到比它小的就做替换；这次遍历中如果遇到比现有的最小值大的，就把它存成次小值；如果之后还有比次小值更大的，说明这个满足题意的三元组一定存在。上述过程也是唯一一种存在该三元组的情况，其他则都返回False。

from typing import List

def increasing_triplet(nums: List[int]):
    min_num, sec_num = float('inf'), float('inf')
    for i in nums:
        min_num = min(i, min_num)
        if i > min_num:
            sec_num = min(i, sec_num)
        if i > sec_num:
            return True
    return False

nums = [5, 4, 3, 2, 1]
print(increasing_triplet(nums))  
# False

力扣747. 至少是其他数字两倍的最大数

与上一题类似，结果是要大于元素其它至少2倍的元素，在一次遍历中找到最大值和次大值进行比较即可。由于要返回下标，使用enumerate（）方法将下标和元素一起遍历。假设较大的元素是max_num，次大的元素是sec_num，一次遍历中，如果元素大于较大元素，那么把它和它的下标存下来；继续遍历如果大于次大元素，则对sec_num更新。如果最终得到的max_num >= 2 * sec_num，则返回较大值的下标，否则为-1。

from typing import List

def dominant_index(nums: List[int]):
    max_num = sec_num = index = -1
    for i, num in enumerate(nums):
        if num > max_num:
            sec_num, max_num, index = max_num, num, i
        elif num > sec_num:
            sec_num = num
        print("num_ele=", sec_num, "num_res=", max_num)
    return index if max_num >= 2 * sec_num else -1

nums = [3, 6, 1, 0]
print(dominant_index(nums))  # 1

END

相关文章