⚡Flashcard Drill➔
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

  1. Greedily push increasing numbers onto a stack. Whenever an I is encountered (or the string ends), flush the stack.
  2. Because D runs must be decreasing, pushing and then flushing at each I produces the longest possible decreasing runs, which minimises the leading digits.
  3. The flush reverses the pushed values, so a run of Ds becomes a decreasing sequence.
  4. 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 D instead of I: the D runs are exactly what must be accumulated and reversed.
  • Forgetting the i == n flush: 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.
🎯 Drill This Card Now➔

🧩 Related Stack Problems