. Maximum Width Ramp

962. Maximum Width Ramp

Difficulty: Medium

Topics: Array, Stack, Monotonic Stack

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:

• 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:

• 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⁴
• 0 <= nums[i] <= 5 * 10⁴

Solution:

We can leverage the concept of a monotonic stack. Here's the solution and explanation:

Approach:

1. Monotonic Decreasing Stack: We create a stack that keeps track of indices of elements in a way such that nums[stack[i]] is in a decreasing order. This allows us to later find pairs (i, j) where nums[i] <= nums[j].
2. Traverse from the End: After creating the stack, we traverse the array from the end (j from n-1 to 0) to try and find the farthest i for each j where nums[i] <= nums[j].
3. Update the Maximum Width: Whenever nums[i] <= nums[j] holds for the current top of the stack, calculate the ramp width j - i and update the maximum width if it's larger.

Let's implement this solution in PHP: 962. Maximum Width Ramp

  
  
  Explanation:




Create a Decreasing Stack:


Iterate through the array and add indices to the stack.
Only add an index if it corresponds to a value that is less than or equal to the value of the last index in the stack. This ensures that values in the stack are in a decreasing order.



Traverse from the End:


As we go backward through the array, for each j, pop indices i from the stack as long as nums[i] <= nums[j].
Calculate the width j - i and update maxWidth.



Why This Works:


By maintaining a decreasing stack of indices, we ensure that when we encounter a j with a larger value, it can give us a larger width j - i when i is popped from the stack.



Time Complexity:


Building the stack takes O(n) time since each index is pushed once.
The traversal from the end and popping indices also takes O(n) since each index is popped at most once.
Overall, the solution runs in O(n) time, which is efficient for input size up to 5 * 10^4.





  
  
  Output:



For nums = [6, 0, 8, 2, 1, 5], the output is 4, corresponding to the ramp (1, 5).
For nums = [9, 8, 1, 0, 1, 9, 4, 0, 4, 1], the output is 7, corresponding to the ramp (2, 9).


Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:


LinkedIn
GitHub



          

            
  

            
        
The above is the detailed content of . Maximum Width Ramp. For more information, please follow other related articles on the PHP Chinese website!