# 2434. Using a Robot to Print the Lexicographically Smallest String
###### tags: `Leetcode` `Medium` `Greedy` `Stack`
Link: https://leetcode.com/problems/using-a-robot-to-print-the-lexicographically-smallest-string/description/
## 思路
核心思想是把String里的每个字母先放在stack里面
然后每次检查stack top的element 看后面有没有更小的字符
最好把所有stack里面的character pop出来
## Code

class Solution {
    public String robotWithString(String s) {
        int n = s.length();
        int[] next = new int[n];
        int small = n-1;
        for(int i=n-1; i>=0; i--){
            next[i] = small;
            if(s.charAt(i)<s.charAt(small)) small = i;
        }
        StringBuilder ans = new StringBuilder();
        Stack<Character> t = new Stack();
        for(int i=0; i<n; i++){
            t.push(s.charAt(i));
            while(!t.isEmpty() && s.charAt(next[i])>=t.peek()){
                ans.append(t.pop());
            }
        }
        while(!t.isEmpty()){
            ans.append(t.pop());
        }
        return ans.toString();
    }
}