问题:最大宽度坡
给定一个整数数组 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.
提示:
2 <= A.length <= 50000
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; }};