LeetCode //C - 962. Maximum Width Ramp

962. Maximum Width Ramp

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 < = n u m s . l e n g t h < = 5 ∗ 10 4 2 <= nums.length <= 5 * 10^4 2<=nums.length<=5∗104
• 0 < = n u m s [ i ] < = 5 ∗ 10 4 0 <= nums[i] <= 5 * 10^4 0<=nums[i]<=5∗104

From: LeetCode
Link: 962. Maximum Width Ramp

Solution:

Ideas:

• Build a monotonic decreasing stack of indices from left to right.
  → Stack keeps positions where nums[i] is a new minimum.
• A smaller left value has the best chance to form the widest ramp later.
• Traverse from the right to left (j from end to start):
  → If nums[stack[top]] <= nums[j], then (stack[top], j) forms a valid ramp.
• Calculate width j - stack[top], update maximum width.
• Pop the index from the stack because earlier j will produce smaller widths.
• Continue until stack is empty or j is done.
• Return the maximum width found.

Code:

intmaxWidthRamp(int* nums,int numsSize){if(numsSize <2)return0;// Monotonic decreasing stack of indicesint*stack =(int*)malloc(numsSize *sizeof(int));int top =-1;// Build stack: store indices where nums[i] is a new minimum from the leftfor(int i =0; i < numsSize;++i){if(top ==-1|| nums[i]< nums[stack[top]]){ stack[++top]= i;}}int maxWidth =0;// Scan from the right, try to widen ramps using the stackfor(int j = numsSize -1; j >=0&& top >=0;--j){// While current value can form a ramp with stack[top]while(top >=0&& nums[stack[top]]<= nums[j]){int width = j - stack[top];if(width > maxWidth) maxWidth = width;--top;// Pop because any earlier j will only give smaller width}}free(stack);return maxWidth;}