这道题很明显,需要用到stack,我一开始的想法是用两个stack,一个存functions,一个存start times,算法如下:
package stack; import java.util.List; import java.util.Stack; public class ExclusiveTimeofFunctions636 { public int[] exclusiveTime(int n, List<String> logs) { int[] res = new int[n]; Stack<Integer> funs = new Stack<>(); Stack<Integer> starts = new Stack<>(); for (int i = 0; i < logs.size(); i++) { String[] logInfo = logs.get(i).split(":"); int currFun = Integer.valueOf(logInfo[0]); int currTime = Integer.valueOf(logInfo[2]); if ("start".equals(logInfo[1])) { if (!funs.isEmpty()) { int lastFun = funs.peek(); int lastStart = starts.peek(); res[lastFun] += currTime - lastStart; } funs.add(currFun); starts.add(currTime); } else { int lastStart = starts.pop(); int lastFun = funs.pop(); res[lastFun] += currTime + 1 - lastStart; if (!funs.isEmpty()) { starts.pop(); starts.add(currTime + 1); } } } return res; } }
上面的算法虽然work,但是稍显繁琐,仔细分析一下,其实start time不需要放在stack中,我们只需要上一个function的开始时间和新的function的开始时间即可,改进算法如下:
class Solution { public int[] exclusiveTime(int n, List<String> logs) { Stack<Integer> funcs = new Stack<>(); int lastStart=0; int[] res = new int[n]; for(String s: logs){ String[] infos = s.split(":"); int func = Integer.valueOf(infos[0]); int time = Integer.valueOf(infos[2]); if(!funcs.empty()){ res[funcs.peek()]+=time-lastStart; } if("start".equals(infos[1])){ funcs.add(func); lastStart = time; }else{ res[funcs.pop()]++; lastStart = time+1; } } return res; } }
以上两个算法的时间和空间复杂度均是O(n).