剑指offer计划27（栈与队列困难）---java（csdn）————程序.pdf

在本篇讨论中，我们将深入理解两种不同的编程问题，它们都涉及到栈与队列的数据结构，以及如何在Java中高效地解决这些问题。我们来看第一个题目，"剑指 Offer 59 - I. 滑动窗口的最大值"。 滑动窗口的最大值问题要求在数组nums中找到所有长度为k的连续子数组的最大值。这里，我们采用一个最大堆（deque）作为主要数据结构。在构建初始窗口时，我们不断从deque中移除比当前元素小的元素，并将当前元素添加到deque的尾部，确保deque始终包含当前窗口内的最大值。一旦初始窗口形成，我们可以通过类似的方式移动窗口，不断更新deque，保持其特性。在每次窗口移动时，我们检查即将离开窗口的元素是否为最大值，如果是，就从deque中移除；然后将新元素与deque尾部的元素比较，如果新元素更大或相等，就将其添加到deque尾部。 以下是实现这个算法的Java代码： ```java class Solution { public int[] maxSlidingWindow(int[] nums, int k) { Deque<Integer> q = new LinkedList<>(); // 形成最初的窗口 for (int i = 0; i <= k - 1; ++i) { while (!q.isEmpty() && q.peekLast() < nums[i]) { q.removeLast(); } q.offerLast(nums[i]); } int[] res = new int[nums.length - k + 1]; res[0] = q.peekFirst(); if (nums[0] == q.peekFirst()) { q.removeFirst(); } // 窗口已经形成 for (int i = k; i <= nums.length - 1; ++i) { while (!q.isEmpty() && q.peekLast() < nums[i]) { q.removeLast(); } q.offerLast(nums[i]); res[i - k + 1] = q.peekFirst(); if (nums[i - k + 1] == q.peekFirst()) { q.removeFirst(); } } return res; } } ``` 接下来，我们看第二个题目，"剑指 Offer 59 - II. 队列的最大值"。此问题要求创建一个队列，支持两个基本操作：`push_back` 和 `pop_front`，同时能提供当前队列中的最大值。我们使用一个普通队列`q`和一个双端队列`d`来实现这个功能。`d`用于存储最大值，而`q`则用于存储所有元素。在`push_back`操作中，我们将新元素与`d`的尾部元素比较，如果新元素更大，就在`d`中移除较小的元素，并将新元素添加到`d`的尾部。`pop_front`操作时，如果`q`的头部元素同时也是`d`的头部元素，我们需要将两者都移除。 以下是这个算法的Java实现： ```java class MaxQueue { Queue<Integer> q; Deque<Integer> d; public MaxQueue() { q = new LinkedList<Integer>(); d = new LinkedList<Integer>(); } public int max_value() { if (d.isEmpty()) { return -1; } return d.peekFirst(); } public void push_back(int value) { while (!d.isEmpty() && d.peekLast() < value) { d.pollLast(); } d.offerLast(value); q.offer(value); } public int pop_front() { if (q.isEmpty()) { throw new RuntimeException("Empty queue"); } int val = q.poll(); if (val == d.peekFirst()) { d.pollFirst(); } return val; } } ``` 总结来说，这两个题目都展示了如何巧妙地利用栈和队列的特性来解决特定问题。第一个问题利用了队列的非严格递减性质来快速获取滑动窗口的最大值，而第二个问题则通过两个队列的配合实现了具有最大值查询功能的队列。这两个解决方案都充分体现了数据结构在实际编程问题中的应用价值。