⚡Flashcard Drill➔
NeetCode #370LC-962MediumStack
← Back to All Problems

#370 · #962 · Maximum Width Ramp(最大宽度坡)

📌 Problem Statement & Constraints

A ramp is a pair (i, j) with i < j and nums[i] <= nums[j]. The width is j - i. Given an array nums, return the maximum width of a ramp, or 0 if none exists. Constraints: 2 <= nums.length <= 5 * 10^4, 0 <= nums[i] <= 5 * 10^4.

💡 Core Algorithmic Approaches

  1. Build a decreasing stack of indices from the left: only indices whose value is smaller than every value seen so far can be the left end of an optimal ramp.
  2. Then scan from the right. For each j, pop stack entries while nums[stack[-1]] <= nums[j] and record j - index as a candidate width.
  3. Popping is safe because the popped indices are smaller than j, and later right ends are even further away -- but they are to the left, so a smaller index can never beat the current width for those.
  4. The total work is O(n).

💻 Benchmark Python3 Implementation

class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        n = len(nums)
        st = []
        for i in range(n):
            # keep only indices that are strictly smaller than all previous ones
            if not st or nums[st[-1]] > nums[i]:
                st.append(i)
        best = 0
        for j in range(n - 1, -1, -1):
            while st and nums[st[-1]] <= nums[j]:
                best = max(best, j - st.pop())   # widest ramp for this left end
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each index is pushed once and popped at most once.
💾 Space Complexity
O(n) for the stack.

⚠️ Interview Pitfalls & Follow-ups

  • Pushing every index: the stack must be strictly decreasing in value, otherwise the scan from the right does not work.
  • Scanning from the left instead of the right: the width is maximised by the largest j, so the right-to-left scan is what makes the greedy correct.
  • Using >= when building the stack: equal values should not be pushed, since the earlier index is always at least as good.
  • Trying a nested loop: O(n^2).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Stack Problems