[Swift Weekly Contest 116]LeetCode962. 最大宽度坡 | Maximum

发布时间：2020-12-14 05:08:46 所属栏目：百科来源：网络整理

导读：Given an array? A ?of integers,a? ramp ?is a tuple? (i,j) ?for which? i j ?and? A[i] = A[j] .? The width of such a?ramp is? j - i . Find the maximum width of a ramp in? A .? If one doesn‘t exist,return 0. Example 1: Input: [6,8,2,1,5]Outp

Given an array?A?of integers,a?ramp?is a tuple?(i,j)?for which?i < j?and?A[i] <= A[j].? The width of such a?ramp is?j - i.

Find the maximum width of a ramp in?A.? If one doesn‘t exist,return 0.

Example 1:

Input: [6,8,2,1,5]
Output: 4 Explanation: The maximum width ramp is achieved at (i,j) = (1,5): A[1] = 0 and A[5] = 5.

Example 2:

Input: [9,9,4,1]
Output: 7 Explanation: The maximum width ramp is achieved at (i,j) = (2,9): A[2] = 1 and A[9] = 1.

Note:

2 <= A.length <= 50000
0 <= A[i] <= 50000

给定一个整数数组?A，坡是元组?(i,j)，其中??i < j?且?A[i] <= A[j]。这样的坡的宽度为?j - i。

找出?A?中的坡的最大宽度，如果不存在，返回 0 。

示例 1：

输入：[6,5]
输出：4
解释：
最大宽度的坡为 (i,5): A[1] = 0 且 A[5] = 5.

示例 2：

输入：[9,1]
输出：7
解释：
最大宽度的坡为 (i,9): A[2] = 1 且 A[9] = 1.

提示：

2 <= A.length <= 50000
0 <= A[i] <= 50000

440ms?

 1 class Solution {
 2     func maxWidthRamp(_ A: [Int]) -> Int {
 3         var val:[Int] = [Int]()
 4         var index:[Int] = [Int]()
 5         var n:Int = A.count
 6         var ans:Int = 0
 7         for i in 0..<n
 8         {
 9             var x:Int = A[i]
10             var left:Int = 0
11             var right:Int = val.count - 1
12             while(left < right)
13             {
14                 var mid:Int = (left + right) / 2
15                 if val[mid] <= x
16                 {
17                     right = mid
18                 }
19                 else
20                 {
21                     left = mid + 1
22                 }
23             }
24             if left <= right && val[left] <= x
25             {
26                 ans = max(ans,i - index[left])
27             }
28             if val.isEmpty || val.last! > x
29             {
30                 val.append(x)
31                 index.append(i)
32             }
33         }
34         return ans
35     }
36 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!