给定一个整数数组 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:
1 2 3 4
| 输入:[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
思路
单调栈+排序+双指针
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| class Solution { public: int maxWidthRamp(vector<int>& A) { int n = A.size(), res = 0, i = 0; stack<pair<int, int>> s; s.push({A[0], 0}); for(i = 1;i < n;++i) { if(A[i] < s.top().first) { s.push({A[i], i}); } } vector<pair<int, int>> arr(n); for(i = 0;i < n;++i) { arr[i] = {A[i], i}; } sort(arr.begin(), arr.end(), [](pair<int, int> x1, pair<int, int> x2) { return x1.first < x2.first || (x1.first==x2.first && x1.second > x2.second); }); i = 0; int t = INT_MAX / 2;; while(i < n) { while(!s.empty() && arr[i].first >= s.top().first ) { t = s.top().second; s.pop(); } res = max(res, arr[i].second - t); ++i; } return res; } };
|