6891. 机器人碰撞 (opens new window)

1.栈模拟

分析：遍历整个数组，判断当前元素是否入栈，同时如果为非入栈元素则执行逻辑。从而保证执行逻辑时，只和当前栈内的元素进行交互，不影响到后续入栈的元素。

❌先一次遍历用栈和队列收集数据，再二次遍历栈和队列进行处理。方法不可取，没有发挥出栈的优势，时间复杂度依然是O(n平方)。

• toright维护向右的机器人。
• 如果当前机器人向左行驶，则与栈顶向右行驶的机器人比较（这里一定能保证栈里所有机器人都为于当前元素的左侧，存在碰撞的可能），健康值小于当前向左机器人，则依次出栈。
  • 如果栈为空，则表明当前向左的机器人把前面所有向右机器人都撞飞了，添加进toleft结果列表。
  • 如果栈不为空，若栈顶等于当前元素，则两个同时撞飞；若栈顶大于当前元素，则向左的机器人被撞飞。

最后将栈内剩余的机器人加入toleft列表，容器根据机器人编号重新排序，并返回输出。

class Solution {
    public List<Integer> survivedRobotsHealths(int[] positions, int[] healths, String directions) {
        List<int[]> toleft=new ArrayList<>();
        Stack<int[]> toright=new Stack<>();
        int[][] nums=new int[positions.length][4];
        for(int i=0;i<nums.length;i++){
            nums[i][0] = positions[i];
            nums[i][1]=healths[i];
            nums[i][2]=directions.charAt(i)=='L'?1:2;
            nums[i][3]=i;
        }
        Arrays.sort(nums, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        for(int i=0;i<nums.length;i++){
            if(nums[i][2]==2){
                toright.push(nums[i]);
            }
            else{
                if(toright.size()==0){
                    toleft.add(nums[i]);
                    continue;
                }
                if(toright.peek()[1]==nums[i][1]){
                    toright.pop();
                }
                else{
                    while(toright.size()>0&&toright.peek()[1]<nums[i][1]){
                        nums[i][1]--;
                        toright.pop();
                    }
                    if(toright.size()==0) toleft.add(nums[i]);
                    else{
                        if(toright.peek()[1]==nums[i][1]) toright.pop();
                        else toright.peek()[1]--;
                    }
                }
            }
        }
        while(toright.size()!=0){
            toleft.add(toright.pop());
        }
        Collections.sort(toleft,new Comparator<int[]>(){
            public int compare(int[] o1,int[] o2){
                return o1[3]-o2[3];
            }
        });
        List<Integer> res=new ArrayList<>();
        for(int[] a:toleft){
            res.add(a[1]);
        }
        return res;

    }
}