下面列出了java.util.ArrayDeque#pollLast ( ) 实例代码,或者点击链接到github查看源代码,也可以在右侧发表评论。
/**
* 滑动窗口应当是队列,但为了得到滑动窗口的最大值,队列序可以从两端删除元素,因此使用双端队列。 对新来的元素k,将其与双端队列中的元素相比较
* 1)前面比k小的,直接移出队列(因为不再可能成为后面滑动窗口的最大值了!), 2)前面比k大的X,比较两者下标,判断X是否已不在窗口之内,不在了,直接移出队列
* 队列的第一个元素是滑动窗口中的最大值
*/
public ArrayList<Integer> maxInWindows(int[] num, int size) {
ArrayList<Integer> list = new ArrayList<>();
if (size == 0) return list;
int start = 0;
// 用来保存可能是滑动窗口最大值的数字的下标
ArrayDeque<Integer> index = new ArrayDeque<>();
for (int i = 0; i < num.length; i++) {
start = i - size + 1;
if (index.isEmpty()) index.add(i);
// 如果队列的头部元素已经从滑动窗口里滑出,滑出的数字需要从队列的头部删除
else if (start > index.peekFirst()) index.pollFirst();
// 数组:{2,3,4,2,6,2,5,1}
// 如果已有数字小于待存入的数据, 这些数字已经不可能是滑动窗口的最大值
// 因此它们将会依次地从队尾删除
while ((!index.isEmpty()) && num[index.peekLast()] <= num[i]) index.pollLast();
index.add(i);
if (start >= 0) list.add(num[index.peekFirst()]);
}
return list;
}
/**
* Builds a sorted list of views. The sorting order depends on the dependencies
* between the view. For instance, if view C needs view A to be processed first
* and view A needs view B to be processed first, the dependency graph
* is: B -> A -> C. The sorted array will contain views B, A and C in this order.
*
* @param sorted The sorted list of views. The length of this array must
* be equal to getChildCount().
* @param rules The list of rules to take into account.
*/
void getSortedViews(View[] sorted, int... rules) {
final ArrayDeque<Node> roots = findRoots(rules);
int index = 0;
Node node;
while ((node = roots.pollLast()) != null) {
final View view = node.view;
final int key = view.getId();
sorted[index++] = view;
final ArrayMap<Node, DependencyGraph> dependents = node.dependents;
final int count = dependents.size();
for (int i = 0; i < count; i++) {
final Node dependent = dependents.keyAt(i);
final SparseArray<Node> dependencies = dependent.dependencies;
dependencies.remove(key);
if (dependencies.size() == 0) {
roots.add(dependent);
}
}
}
if (index < sorted.length) {
throw new IllegalStateException("Circular dependencies cannot exist"
+ " in RelativeLayout");
}
}
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
// 特判
if (len == 0) {
return new int[]{};
}
// 结果集
List<Integer> res = new ArrayList<>();
// 滑动窗口,注意:保存的是索引值
ArrayDeque<Integer> deque = new ArrayDeque<>(k);
for (int i = 0; i < len; i++) {
// 当元素从左边界滑出的时候,如果它恰恰好是滑动窗口的最大值
// 那么将它弹出
if (i >= k && i - k == deque.getFirst()) {
deque.pollFirst();
}
// 如果滑动窗口非空,新进来的数比队列里已经存在的数还要大
// 则说明已经存在数一定不会是滑动窗口的最大值(它们毫无出头之日)
// 将它们弹出
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
deque.pollLast();
}
deque.add(i);
// 队首一定是滑动窗口的最大值的索引
if (i >= k - 1) {
res.add(nums[deque.peekFirst()]);
}
}
int size = res.size();
int[] result = new int[size];
for (int i = 0; i < size; i++) {
result[i] = res.get(i);
}
return result;
}
/**
* peekFirst() returns element inserted with push
*/
public void testPush() {
ArrayDeque q = populatedDeque(3);
q.pollLast();
q.push(four);
assertSame(four, q.peekFirst());
}
/**
* peekFirst() returns element inserted with push
*/
public void testPush() {
ArrayDeque q = populatedDeque(3);
q.pollLast();
q.push(four);
assertSame(four, q.peekFirst());
}
/**
* TODO: each thread should hold local reference to own deque
* @return a task, or null if nothing available
*/
public Task getTask(int threadNum) {
// Targeted have highest priority
Task res = targeted.get(threadNum).pollLast();
if (res != null)
return res;
// Next, try to see if something in local deque
ArrayDeque<Task> myDeque = regular.get(threadNum);
synchronized (myDeque) {
res = myDeque.pollLast();
}
if (res != null)
return res;
// Finally, search other deques to steal work
// TODO: exit condition - detect idle, or go to sleep
Random r = new Random();
while (true) {
int deque = r.nextInt(numThreads - 1);
if (deque >= threadNum)
deque++;
ArrayDeque<Task> otherDeque = regular.get(threadNum);
// Task from other end
synchronized (otherDeque) {
res = otherDeque.pollFirst();
}
if (res != null)
return res;
}
}