当前位置: 代码迷 >> 综合 >> leetcode 962. Maximum Width Ramp
  详细解决方案

leetcode 962. Maximum Width Ramp

热度:76   发布时间:2024-01-16 17:59:33.0

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;}
};

 

  相关解决方案