leetcode 962. Maximum Width Ramp
题意:求一个数组A里面,满足i<j && A[i]<=A[j],并且j-i最大。不存在返回0。
思路:dp[i] 表示最后一个大于等于i的位置。
class Solution {
public:int maxWidthRamp(vector<int>& A) {vector<int> dp(500001,-1); for (int i = 0; i < A.size(); i++)dp[A[i]] = i;for (int i = 500000; i >= 0; i--)dp[i] = max(dp[i],dp[i + 1]);int ans = 0;for (int i = 0; i < A.size(); i++)ans = max(ans, dp[A[i]] - i);return ans;}};
思路2:从左往右生成单调队列,从右往左找。
class Solution {
public:int maxWidthRamp(vector<int>& A) {stack<int> s;for (int i = 0; i < A.size(); i++) {if (s.empty() || A[s.top()] > A[i]) {s.push(i);}}int res = 0, t;for (int i = A.size() - 1; i >= 0; i--) {while (!s.empty() && A[s.top()] <= A[i]) {t = i - s.top();res = max(res, t);s.pop();}}return res;}
};