给定一个整数数组 asteroids,表示在同一行的小行星。
对于数组中的每一个元素,其绝对值表示小行星的大小,正负表示小行星的移动方向(正表示向右移动,负表示向左移动)。每一颗小行星以相同的速度移动。
找出碰撞后剩下的所有小行星。碰撞规则:两个行星相互碰撞,较小的行星会爆炸。如果两颗行星大小相同,则两颗行星都会爆炸。两颗移动方向相同的行星,永远不会发生碰撞。
class Solution { public int[] asteroidCollision(int[] asteroids) { Deque<Integer> sta = new LinkedList<>(); for(int a : asteroids){ if(!sta.isEmpty() && sta.peekLast()>0 && a < 0){ boolean disappear = false; // while的目的是为了持续向左撞 while(!sta.isEmpty() && sta.peekLast() > 0 && a < 0){ int peng = sta.peekLast() + a; if(peng == 0){ disappear = true; sta.pollLast(); // sta.pollLast(); break; }else if(peng > 0){ disappear = true; // sta.pollLast(); break; }else { sta.pollLast(); break; } } if(disappear == false){ sta.addLast(a); } }else{ sta.addLast(a); } } int n = sta.size(); int[] res = new int[n]; for(int i = 0; i < n; i++){ res[i] = sta.pollFirst(); } return res; } }
这里使用for以deque.size()为限制条件会出问题,因为拿出是以从队列拿出的方式,所以deque的长度发生了变化会少值
普通队列(一端进另一端出):
Queue queue = new LinkedList()或Deque deque = new LinkedList()
双端队列(两端都可进出)
Deque deque = new LinkedList()
堆栈
Deque deque = new LinkedList()
第一个元素 (头部) 最后一个元素 (尾部)
抛出异常 特殊值 抛出异常 特殊值
插入 addFirst(e) offerFirst(e) addLast(e) offerLast(e)
删除 removeFirst() pollFirst() removeLast() pollLast()
检查 getFirst() peekFirst() getLast() peekLast()