LeetCode 962. 最大宽度坡 C 语言解法

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 <= nums.length <= 5 * 10^4
• 0 <= nums[i] <= 5 * 10^4

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:

int maxWidthRamp(int* nums, int numsSize) {
    if (numsSize < 2) return 0;

    // Monotonic decreasing stack of indices
    int* stack = (int*)malloc(numsSize * sizeof(int));
    int top = -1;

    // Build stack: store indices where nums[i] is a new minimum from the left
    for (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 stack
    for (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;
}