队列sliding-window-maximum-leetcode练习题

小灰灰 2023-07-23 03:49 1阅读 0赞

import java.io.BufferedReader;
 import java.io.IOException;
 import java.io.InputStreamReader;
 import java.util.Comparator;
 import java.util.PriorityQueue;
 
 /**
 * 给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
 * 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 * 
 * 返回滑动窗口中的最大值。
 * 
 * 进阶：
 * 你能在线性时间复杂度内解决此题吗？
 * 
 * 示例:
 * 
 * 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
 * 输出: [3,3,5,5,6,7]
 * 
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sliding-window-maximum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
 class Solution {
 /**
 * 暴力法
 *
 * @param nums
 * @param k
 * @return
 */
 public int[] maxSlidingWindow2(int[] nums, int k) {
 int n = nums.length;
 if (n * k == 0) return new int[0];
 
 int[] output = new int[n - k + 1];
 for (int i = 0; i < n - k + 1; i++) {
 int max = Integer.MIN_VALUE;
 for (int j = i; j < i + k; j++)
 max = Math.max(max, nums[j]);
 output[i] = max;
 }
 return output;
 }
 
 /**
 * 优先级队列
 *
 * @param nums
 * @param k
 * @return
 */
 public int[] maxSlidingWindow(int[] nums, int k) {
 if (nums == null || nums.length < k) {
 return new int[0];
 }
 int[] res = new int[nums.length - k + 1];
 PriorityQueue<Integer> pq = null;
 for (int i = 0; i < nums.length - k + 1; i++) {
 pq = new PriorityQueue<>(k, Comparator.reverseOrder());
 for (int j = i; j < i + k; j++) {
 pq.add(nums[j]);
 if (j == i + k - 1) {
 res[j - k + 1] = pq.remove();
 }
 }
 
 }
 return res;
 }
 }
 
 public class MainClass {
 public static int[] stringToIntegerArray(String input) {
 input = input.trim();
 input = input.substring(1, input.length() - 1);
 if (input.length() == 0) {
 return new int[0];
 }
 String[] parts = input.split(",");
 int[] output = new int[parts.length];
 for (int index = 0; index < parts.length; index++) {
 String part = parts[index].trim();
 output[index] = Integer.parseInt(part);
 }
 return output;
 }
 
 public static String integerArrayToString(int[] nums, int length) {
 if (length == 0) {
 return "[]";
 }
 String result = "";
 for (int index = 0; index < length; index++) {
 int number = nums[index];
 result += Integer.toString(number) + ", ";
 }
 return "[" + result.substring(0, result.length() - 2) + "]";
 }
 
 public static String integerArrayToString(int[] nums) {
 return integerArrayToString(nums, nums.length);
 }
 
 public static void main(String[] args) throws IOException {
 BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 String line;
 while ((line = in.readLine()) != null) {
 int[] nums = stringToIntegerArray(line);
 line = in.readLine();
 int k = Integer.parseInt(line);
 int[] ret = new Solution().maxSlidingWindow(nums, k);
 String out = integerArrayToString(ret);
 System.out.print(out);
 }
 }
 }

大神的双端队列解法

ArrayDeque<Integer> deq = new ArrayDeque<Integer>();
 int[] nums;
 
 public void clean_deque(int i, int k) {
 // remove indexes of elements not from sliding window
 if (!deq.isEmpty() && deq.getFirst() == i - k)
 deq.removeFirst();
 
 // remove from deq indexes of all elements
 // which are smaller than current element nums[i]
 while (!deq.isEmpty() && nums[i] > nums[deq.getLast()]) deq.removeLast();
 }
 
 public int[] maxSlidingWindow3(int[] nums, int k) {
 int n = nums.length;
 if (n * k == 0) return new int[0];
 if (k == 1) return nums;
 
 // init deque and output
 this.nums = nums;
 int max_idx = 0;
 for (int i = 0; i < k; i++) {
 clean_deque(i, k);
 deq.addLast(i);
 // compute max in nums[:k]
 if (nums[i] > nums[max_idx]) max_idx = i;
 }
 int[] output = new int[n - k + 1];
 output[0] = nums[max_idx];
 
 // build output
 for (int i = k; i < n; i++) {
 clean_deque(i, k);
 deq.addLast(i);
 output[i - k + 1] = nums[deq.getFirst()];
 }
 return output;
 }

处理前 k 个元素，初始化双向队列。

遍历整个数组。在每一步 :

清理双向队列 :

- 只保留当前滑动窗口中有的元素的索引。

- 移除比当前元素小的所有元素，它们不可能是最大的。

将当前元素添加到双向队列中。  
    将 deque\[0\] 添加到输出中。  
    返回输出数组。