首页 > 其他分享 >LeetCode 1014. 最佳观光组合

LeetCode 1014. 最佳观光组合

时间:2024-09-24 10:23:57浏览次数:9  
标签:int 观光 Solution values 景点 1014 LeetCode

题目简介:

给你一个正整数数组 values,其中 values[i] 表示第 i 个观光景点的评分,并且两个景点 i 和 j 之间的 距离 为 j - i

一对景点(i < j)组成的观光组合的得分为 values[i] + values[j] + i - j ,也就是景点的评分之和 减去 它们两者之间的距离。

返回一对观光景点能取得的最高分。

解题方法:

用两个变量,ans,maxval分别记录最优路线和最优起点,每当循环遍历一次,那么最优起点的值应当减一(这是由于距离增加带来的起点的在组合中评分降低)。

时间复杂度为:O(n)

空间复杂度为:O(1)

public class question_1014 {
    public static void main(String[] args) {
        int[] arr = {8,1,5,2,6};
        Solution_1014 solution1014= new Solution_1014();
        System.out.println(solution1014.maxScoreSightseeingPair(arr));
    }
}
class Solution_1014 {
    public int maxScoreSightseeingPair(int[] values) {
        int ans = 0;
        int maxval = values[0] - 1;
        for(int i = 1; i<values.length ;i++){
            //记录评分较高观光组合
            ans = Math.max(ans,values[i] + maxval);
            //-1,每次循环距离加1,评分减一,maxval保存评分较高的景点
            maxval = Math.max(maxval,values[i]) - 1;
        }
        return ans;
    }
}

标签:int,观光,Solution,values,景点,1014,LeetCode
From: https://blog.csdn.net/2302_77430843/article/details/142448466

相关文章

  • Day 23 贪心算法part01| LeetCode 455.分发饼干,376.摆动序列,53.最大子序和
    455.分发饼干455.分发饼干classSolution{publicintfindContentChildren(int[]g,int[]s){Arrays.sort(g);Arrays.sort(s);intindex=s.length-1;intcount=0;for(inti=g.le......
  • 387. 字符串中的第一个唯一字符-LeetCode(C++)
    387.字符串中的第一个唯一字符题目给定一个字符串s,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回-1。提示:1<=s.length<=105s只包含小写字母示例示例1:输入:s="leetcode"输出:0示例2:输入:s="loveleetcode"输出:2示例3:......
  • leetcode刷题day27|贪心算法Part01(455.分发饼干、376. 摆动序列、53. 最大子序和)
    前言:贪心的本质选择每一阶段的局部最优,从而达到全局最优。455.分发饼干思路:局部最优-大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个;全局最优:喂饱尽可能多的小孩。可以尝试使用贪心策略,先将饼干数组和小孩数组排序,然后从后向前遍历小孩数组,用大饼干优先满足胃口大的,并统计......
  • LeetCode Hot 100
    1Tree1.1Recursion1.1RecursionPreOrderTraversalhttps://leetcode.cn/problems/binary-tree-preorder-traversal/#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,val=0,left=None,right=None):#self.val=val......
  • Leetcode 65. 有效数字
    1.题目基本信息1.1.题目描述给定一个字符串s,返回s是否是一个有效数字。例如,下面的都是有效数字:”2″,“0089”,“-0.1”,“+3.14”,“4.”,“-.9”,“2e10”,“-90E3”,“3e+7”,“+6e-1”,“53.5e93”,“-123.456e789″,而接下来的不是:”abc”,“1a”,“1e”......
  • 1014.最佳观光组合
    给你一个正整数数组values,其中values[i]表示第i个观光景点的评分,并且两个景点i和j之间的距离为j-i。一对景点(i<j)组成的观光组合的得分为values[i]+values[j]+i-j,也就是景点的评分之和减去它们两者之间的距离。返回一对观光景点能取得的最高分。示例......
  • 计算机低能儿从0刷leetcode | 11.盛最多水的容器
    题目:11.盛最多水的容器解答:不想暴力遍历,于是让右端点j从最右侧开始遍历,每次寻找离j最远、且高度不小于height[j]的左端点i,结果发现错误,比如[1,2]的情况。于是又打补丁,按同样思路左端点i从0开始遍历,每次寻找离i最远、且高度不小于height[i]的右端点j,结果正确,然而时间复杂度......
  • 数据结构之线性表——LeetCode:328. 奇偶链表,86. 分隔链表,24. 两两交换链表中的节点
    328.奇偶链表题目描述328.奇偶链表给定单链表的头节点 head ,将所有索引为奇数的节点和索引为偶数的节点分别组合在一起,然后返回重新排序的列表。第一个节点的索引被认为是 奇数 , 第二个节点的索引为 偶数 ,以此类推。请注意,偶数组和奇数组内部的相对顺序应该与输......
  • 数据结构之线性表——LeetCode:80. 删除有序数组中的重复项 II,88. 合并两个有序数组,4.
    80.删除有序数组中的重复项II题目描述80.删除有序数组中的重复项II给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使得出现次数超过两次的元素只出现两次 ,返回删除后数组的新长度。不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用O(1)额外......
  • 数据结构之线性表——LeetCode:82. 删除排序链表中的重复元素 II,21. 合并两个有序链
    82.删除排序链表中的重复元素II题目描述82.删除排序链表中的重复元素II给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。运行代码classSolution{public:ListNode*deleteDuplicates(ListNode......