Java Stack Solution O(n) Time O(n) Space


  • 11
    public int[] exclusiveTime(int n, List<String> logs) {
        int[] res = new int[n];
        Stack<Integer> stack = new Stack<>();
        int prevTime = 0;
        for (String log : logs) {
            String[] parts = log.split(":");
            if (!stack.isEmpty()) res[stack.peek()] +=  Integer.parseInt(parts[2]) - prevTime; 
            prevTime = Integer.parseInt(parts[2]);
            if (parts[1].equals("start")) stack.push(Integer.parseInt(parts[0]));
            else {
                res[stack.pop()]++;
                prevTime++;
            }
        }
        return res;
    }
    

  • 6
    G

    Add some explanation. Thanks for your idea.

    public int[] exclusiveTime(int n, List<String> logs) {
        // separate time to several intervals, add interval to their function
        int[] result = new int[n];
        Stack<Integer> st = new Stack<>();
        int pre = 0;
        // pre means the start of the interval
        for(String log: logs) {
            String[] arr = log.split(":");
            if(arr[1].equals("start")) {
                if(!st.isEmpty())  result[st.peek()] += Integer.parseInt(arr[2]) - pre;
                // arr[2] is the start of next interval, doesn't belong to current interval.
                st.push(Integer.parseInt(arr[0]));
                pre = Integer.parseInt(arr[2]);
            } else {
                result[st.pop()] += Integer.parseInt(arr[2]) - pre + 1;
                // arr[2] is end of current interval, belong to current interval. That's why we have +1 here
                pre = Integer.parseInt(arr[2]) + 1;
                // pre means the start of next interval, so we need to +1
            }
        }
        return result;
    }

  • 0

    Another Approach.

    public int[] exclusiveTime(int n, List<String> logs) {
        int [] ans = new int [n];
        Stack <int []> stack = new Stack <>();
        int prev = 0;
        for (String log : logs) {
            int id = Integer.valueOf (log.split (":") [0]), time = Integer.valueOf (log.split (":") [2]);
            String action = log.split (":") [1];
            if (action.equals("start")) {
                if (!stack.isEmpty()) stack.peek () [1] += (time - prev - 1);
                stack.push (new int [] { id, 1 });
            } else ans [stack.peek () [0]] += stack.pop () [1] + (time - prev);
            prev = time;
        }
        return ans;
    }
    

  • 0
    N

    @GardenAAA good explanation, thanks


  • 0
    Z

    nice,the logic is clear


  • 0
    M

    Good idea to make it concise. Implement your idea in C++

    class Solution {
    public:
        vector<int> exclusiveTime(int n, vector<string>& logs) { 
            vector<int> result(n, 0);
            stack<int> sk;
            int prev_time = 0;
            for(const string& log:logs) {
                bool start = true;
                int id = 0, time = 0;
                decompose(log, start, id, time);
                if(!sk.empty()) result[sk.top()] += time-prev_time;
                prev_time = time;
                if(start) {
                    sk.push(id);
                }
                else {
                    result[sk.top()]++;
                    prev_time++;
                    sk.pop();
                }
            }
            return result;
        }
    private:
        void decompose(const string& log, bool& start, int& id, int& time) {
            int i = 0;
            while(log[i]!=':') i++;
            id = stoi(log.substr(0,i));
            start = true;
            if(log[++i]=='e') start=false;
            if(start) time = stoi(log.substr(i+6, log.length()-i-6));
            else time = stoi(log.substr(i+4, log.length()-i-4));
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.