NeetCode #364LC-484MediumStackNC Algo100
← Back to All Problems#364 · #484 · Find Permutation(寻找排列)
📌 Problem Statement & Constraints
A permutation
perm of 1..n can be derived from a string s of length n - 1: s[i] == 'I' means perm[i] < perm[i+1] and s[i] == 'D' means perm[i] > perm[i+1]. Return the lexicographically smallest such permutation. Constraints: 1 <= s.length <= 10^4.💡 Core Algorithmic Approaches
- Greedily push increasing numbers onto a stack. Whenever an
Iis encountered (or the string ends), flush the stack. - Because
Druns must be decreasing, pushing and then flushing at eachIproduces the longest possible decreasing runs, which minimises the leading digits. - The flush reverses the pushed values, so a run of
Ds becomes a decreasing sequence. - This yields the lexicographically smallest permutation by construction.
💻 Benchmark Python3 Implementation
class Solution:
def findPermutation(self, s: str) -> List[int]:
n = len(s)
res = []
st = []
for i in range(n + 1):
st.append(i + 1) # next candidate number
if i == n or s[i] == "I": # flush the pending decreasing run
while st:
res.append(st.pop())
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each number is pushed and popped once.
💾 Space Complexity
O(n) for the stack and the result.
⚠️ Interview Pitfalls & Follow-ups
- Flushing on
Dinstead ofI: theDruns are exactly what must be accumulated and reversed. - Forgetting the
i == nflush: the final run would never be emitted. - Using a sort at the end: the construction already yields the lexicographically smallest result; sorting would destroy it.
- Starting the numbers at 0: the permutation is over
1..n.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.