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
- 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.
- Then scan from the right. For each
j, pop stack entries whilenums[stack[-1]] <= nums[j]and recordj - indexas a candidate width. - 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. - 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.