Skip to content

962. Maximum Width Ramp 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  int maxWidthRamp(vector<int>& nums) {
    int ans = 0;
    stack<int> stack;

    for (int i = 0; i < nums.size(); ++i)
      if (stack.empty() || nums[i] < nums[stack.top()])
        stack.push(i);

    for (int i = nums.size() - 1; i > ans; --i)
      while (!stack.empty() && nums[i] >= nums[stack.top()])
        ans = max(ans, i - stack.top()), stack.pop();

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public int maxWidthRamp(int[] nums) {
    int ans = 0;
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < nums.length; ++i)
      if (stack.isEmpty() || nums[i] < nums[stack.peek()])
        stack.push(i);

    for (int i = nums.length - 1; i > ans; --i)
      while (!stack.isEmpty() && nums[i] >= nums[stack.peek()])
        ans = Math.max(ans, i - stack.pop());

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def maxWidthRamp(self, nums: List[int]) -> int:
    ans = 0
    stack = []

    for i, num in enumerate(nums):
      if stack == [] or num <= nums[stack[-1]]:
        stack.append(i)

    for i, num in reversed(list(enumerate(nums))):
      while stack and num >= nums[stack[-1]]:
        ans = max(ans, i - stack.pop())

    return ans