Leetcode 11 -- 贪心

题目描述

最小字典许

思路

思路来源
由于t中的字符后进先出，可以使用一个暂存栈来保存s删除的第一个字符
入栈很简单，初始状态下，栈为空，我们可以直接入栈，因此，每次遍历我们都是先把元素放入栈中，然后判断是否能出栈
问题是什么时候让元素出栈
贪心的想，如果一个元素要出栈，那么s中剩下的元素不能存在比当前栈顶元素更小的元素
那么问题就变成了如何判断s中是否存在比当前元素更小的元素呢？
最好的办法就是使用一个额外数组来记录每个元素的个数，然后遍历s的时候动态维护

代码

class Solution {
public:
    string robotWithString(string s) {
        // 由于t中的字符后进先出，可以使用一个暂存栈来保存s删除的第一个字符
        // 入栈很简单，问题是什么时候让元素出栈
        // 贪心的想，如果一个元素要出栈，那么s中剩下的元素不能存在比当前栈顶元素更小的元素
        // 那么问题就变成了如何判断s中是否存在比当前元素更小的元素呢？
        // 最好的办法就是使用一个额外数组来记录每个元素的个数，然后遍历s的时候动态维护
        
        stack<char> st;
        int cnt[26];
        int minx = 0; // 剩余的最小字母
        int n = s.length();
        string res = "";
        
        // 计算每个字母的数量
        memset(cnt, 0, sizeof cnt);
        for(auto &ch : s)   ++ cnt[ch - 'a'];
        
        // 遍历s
        for(auto &ch : s)
        {
            -- cnt[ch - 'a']; // 先维护
            while(minx < 26 && cnt[minx] == 0)     ++ minx; // 找到最小元素
            st.push(ch);
            while(!st.empty() && st.top() - 'a' <= minx)
            {
                res += st.top();
                st.pop();
            }
        }
        return res;
    }
};