- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址:https://leetcode.com/problems/best-sightseeing-pair/
Given an array A
of positive integers, A[i]
represents the value of the i
-th sightseeing spot, and two sightseeing spots i
and j
have distance j - i
between them.
Thescore of a pair (i < j
) of sightseeing spots is (A[i] + A[j] + i - j
) : the sum of the values of the sightseeing spots, minus the distance between them.
Return the maximum score of a pair of sightseeing spots.
Example 1:
Input: [8,1,5,2,6]
Output: 11
Explanation: i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11
Note:
1、 2<=A.length<=50000
;
2、 1<=A[i]<=1000
;
对于数组中的两个下标i, j,求A[i] + A[j] + i - j
最大值.
一般暴力解法是两重循环,即先找到一个位置 i
之后,从其后位置 j
继续循环遍历,这样的复杂度是O(N ^ 2)
的。看到题目给出的数据范围,数组的长度是 50000, 对于这个题O(N ^ 2)
的时间复杂度肯定不可取。
对于这个题,我们知道肯定只能用 O(N)
的解法,把公式稍加变化成(A[i] + i) + (A[j] - j)
,我们可以看出要找出这两部分和的最大值。
具体方法是保存每个位置 j
,时刻维护其前面的A[i] + i
的最大值出现的位置 pre_i
。最后结果就是对于每个位置j
对应的A[i] + A[j] + i - j
最大值。
Python代码如下:
class Solution(object):
def maxScoreSightseeingPair(self, A):
"""
:type A: List[int]
:rtype: int
"""
pre_i = 0
res = 0
for j in range(1, len(A)):
res = max(A[j] - j + A[pre_i] + pre_i, res)
if A[j] + j > A[pre_i] + pre_i:
pre_i = j
return res
1 2 3 4 5 6 7 8 9 10 11 12 13
参考资料:https://leetcode.com/problems/best-sightseeing-pair/discuss/260850/JavaC%2B%2BPython-One-Pass
2022
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
题目地址:https://leetcode.com/problems/best-sightseeing-pair/ 题目描述 Given an array A of positive intege
这里是真正的初学者,我正在阅读 NF 和 WHNF 之间的差异,以及我遇到的定义之一 To determine whether an expression is in weak head normal
我正在尝试在没有最外层变量的情况下在 d3.js 中绘制包布局。我想绘制一个没有最外层父圆的包装布局。有什么办法吗? 最佳答案 是的,有。我建议采用以下方法:保持所有圆包初始化完好无损。您只需更改圆圈
我正在使用 dojo.query,它在内部使用 CSS3 选择器来识别您要检索的元素。 我要查找的是所有带有标签“foo”的元素,但仅限于最外层的元素(即允许将一个“foo”嵌入到另一个元素中,而我想
在Java Language Spex 15.7 : Code is usually clearer when each expression contains at most one side ef
在 django 1.5 天,如果我想手动管理事务(或事务中的事务),我会这样做: @transaction.commit_manually def my_method(): master_s
我一直在阅读 C++ 入门第 5 版。在第 6.1 章功能参数列表的第三段中。它写道“此外,函数最外层范围内的局部变量不得使用与任何参数相同的名称”。什么意思? 我不是以英语为母语的人。我不明白函数的
我是一名优秀的程序员,十分优秀!