博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LeetCode962. 最大宽度坡
阅读量:5093 次
发布时间:2019-06-13

本文共 3215 字,大约阅读时间需要 10 分钟。

问题:最大宽度坡

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

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

 

示例 1:

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

示例 2:

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

 

提示:

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

 

链接:https://leetcode-cn.com/contest/weekly-contest-116/problems/maximum-width-ramp/

分析:

问题不难,早早的就有了思路 ,可惜一直卡在50000数组超时上 ,好在不断优化(或者Server突然性能给力?)最后十来分钟AC了。

想要找到最大的j-i,满足i<j且A[i]<=A[j]。

基本思路就是二重循环,但是要做一些优化。

1.如果找到了一组符合要求的n1,n2,那么对于后续的m1>n1,其下限m2必须大于n2,才有可能m2-m1>n2-n1(m1>n1) [通过数轴会更直观一些]

2.如果已经有了符合要求的n1,n2,那么对于n11>n1,如果A[n11]>=A[n1],则没必要看,其结果必定小于n1, 比如下标i1,i2,i3依次递增,如果A[i1]<=A[i2],A[i2]<=A[i3],那么A[i1]<=A[i3],i3-i1>i3-i2

3.在第二层循环的时候, 不但对下限有要求,而且m2-m1要大于已知的最大宽度。

AC Code:

 

class Solution {public:int maxWidthRamp(vector
& A) { int ret = 0; int rightlimit = 0; int predata = -1; for (unsigned int i = 0; i < A.size(); i++) { if (predata == -1) { predata = A[i]; } else { if (predata > A[i]) { predata = A[i]; } else { continue; } } if (A.size() - 1 - i < ret) { return ret; } for (unsigned int j = A.size()-1; j > rightlimit && j-i>ret; j--) { steps++; if (A[j] >= A[i]) { if (j - i > ret) { ret = j - i; } rightlimit = j; break; } } } return ret; } };

虽然AC了,完赛后查看通过时间,98个测例,用时1880ms,还有很大的优化空间。

其他:

1.第一code:

class Solution:    def maxWidthRamp(self, A):        """        :type A: List[int]        :rtype: int        """        l = []        for i in range(len(A)):            l.append((A[i], i))        l.sort()        res = 0        small = l[0][1]        for _,e in l:            if e < small:                small = e            else:                if e - small > res:                    res = e - small        return res

刚注意到国内和国外排行榜是分离的,国际版第一code:

#include
#include
#include
#include
#include
#include
using namespace std;typedef long long LL;typedef vector
VI;#define REP(i,n) for(int i=0, i##_len=(n); i
inline void amin(T &x, const T &y) { if (y
inline void amax(T &x, const T &y) { if (x
void rprintf(const char *fmt, Iter begin, Iter end) { for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); } putchar('\n');}class Solution {public: int maxWidthRamp(vector
& A) { vector
> t; REP (i, A.size()) t.emplace_back(A[i], i); sort(t.begin(), t.end()); int ans = 0; int left = t[0].second; for (int i=1; i<(int)t.size(); i++) { amax(ans, t[i].second - left); amin(left, t[i].second); } return ans; }};

 

转载于:https://www.cnblogs.com/youdias/p/10163905.html

你可能感兴趣的文章
JVM笔记——技术点汇总
查看>>
iOS中Storyboard使用要点记录
查看>>
入手腾龙SP AF90mm MACRO
查看>>
ORACLE 递归查询
查看>>
20172315 2017-2018-2 《程序设计与数据结构》实验三报告
查看>>
centos虚拟机克隆
查看>>
【Python】:拓展Queue实现有序不重复队列
查看>>
ehcache讲解及实例
查看>>
ajax java base64 图片储存
查看>>
django1.10.3下admin后台管理老是显示object
查看>>
推荐一个程序员阅读文章资料时的辅助神器
查看>>
http://www.jb51.net/article/51934.htm
查看>>
linux查看防火墙状态及开启关闭命令
查看>>
Java集合——TreeMap源码详解
查看>>
2015,鬼王Xun和GGL比赛,带给我们无尽的欢乐
查看>>
111... 南邮NOJ 1079
查看>>
别把SEO当苦力活,做优化要讲究策略
查看>>
Django项目:CRM(客户关系管理系统)--41--33PerfectCRM实现King_admin编辑整张表限制
查看>>
关于时间
查看>>
面向对象 阶段性总结
查看>>