Maximum Width Ramp Problem


Description

LeetCode Problem 962.

A ramp in an integer array nums is a pair (i, j) for which i < j and nums[i] <= nums[j]. The width of such a ramp is j - i.

Given an integer array nums, return the maximum width of a ramp in nums. If there is no ramp in nums, return 0.

Example 1:

1
2
3
Input: nums = [6,0,8,2,1,5]
Output: 4
Explanation: The maximum width ramp is achieved at (i, j) = (1, 5): nums[1] = 0 and nums[5] = 5.

Example 2:

1
2
3
Input: nums = [9,8,1,0,1,9,4,0,4,1]
Output: 7
Explanation: The maximum width ramp is achieved at (i, j) = (2, 9): nums[2] = 1 and nums[9] = 1.

Constraints:

  • 2 <= nums.length <= 5 * 10^4
  • 0 <= nums[i] <= 5 * 10^4


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        if (nums.size() < 2)
            return 0;
        int ans = 0, n = nums.size()-1;
        stack<int> st;
        for (int j = 0; j < nums.size(); j++) {
            if (st.empty() || nums[j] < nums[st.top()])
                st.push(j);
        }
        for (int i = n; i > ans; i--) {
            while (!st.empty() && nums[i] >= nums[st.top()]) {
                ans = max(ans, i - st.top());
                st.pop();
            }
        }
        return ans;
    }
};




Related Posts

Validate Stack Sequences Problem

LeetCode 946. Given two integer arrays pushed and popped each...

Stamping The Sequence Problem

LeetCode 936. You are given two strings stamp and target....

Score Of Parentheses Problem

LeetCode 856. Given a balanced parentheses string s, return the...

Minimum Add To Make Parentheses Valid Problem

LeetCode 921. A parentheses string is valid if and only...

Maximum Width Ramp Problem

LeetCode 962. A ramp in an integer array nums is...

Decoded String At Index Problem

LeetCode 880. You are given an encoded string s. To...