给定一个整数数组 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
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-width-ramp 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
[9,8,1,0,1,9,4,0,4,1]
class Solution { //错误解
public:
int maxWidthRamp(vector<int>& A) {
deque<int> q;
int maxlen = 0;
for(int i = 0; i < A.size(); ++i)
{
while(!q.empty() && A[q.back()] > A[i])
q.pop_back();
if(!q.empty())
maxlen = max(maxlen, i-q.front());
q.push_back(i);
}
return maxlen;
}
};
class Solution {
public:
int maxWidthRamp(vector<int>& A) {
stack<int> s;
int maxlen = 0, i;
for(i = 0; i < A.size(); ++i)
{
if(s.empty() || A[s.top()] > A[i])//单调递减栈
s.push(i);
}
for(i = A.size()-1; i >= 0; --i)
{
while(!s.empty() && A[i] >= A[s.top()])
{
maxlen = max(maxlen, i-s.top());
s.pop();
}
}
return maxlen;
}
};
136 ms 28.1 MB