滑动窗口中的最大值

滑动窗口中的最大值

问题

这个题目说的是，给你一个整数数组和整数 k，k 表示滑动窗口的大小，滑动窗口从左向右滑过数组，每移动一个位置，你要计算出当前滑动窗口内 k 个数字的最大值。最后返回这个最大值数组。

比如说，给你的数组是 0, 4, 2, 1, 0, 8, 2，给你的滑动窗口大小 k 等于 3。我们使用大小为 3 的滑动窗口，来找到这个最大值序列。

* 第一个滑动窗口内的数字是 0, 4, 2，最大值为 4
* 移动窗口，窗口内数字变为 4, 2, 1，最大值仍然为 4
* 继续移动窗口，窗口内数字变为 2, 1, 0，最大值变为 2
* 接着移动窗口，窗口内数字变为 1, 0, 8，最大值变为 8
* 继续移动窗口，最后窗口内的数字变为 0, 8, 2，最大值仍然是 8

这时滑动窗口再移动的话，窗口内的数字就不足 k 个，于是结束处理过程。最后就得到了最大值数组 4, 4, 2, 8, 8。

代码

public class AlgoCasts {

  // Time: O(k*n), Space: O(1)
  public int[] maxNumInSlidingWindowBruteForce(int[] nums, int k) {
    if (nums == null || nums.length == 0) return nums;
    int n = nums.length;
    int[] result = new int[n - k + 1];
    for (int left = 0; left <= n-k; ++left) {
      int max = nums[left];
      for (int i = left; i < left+k; ++i) {
        max = Math.max(max, nums[i]);
      }
      result[left] = max;
    }
    return result;
  }

  // Time: O(n*log(k)), Space: O(k)
  public int[] maxNumInSlidingWindowTreeMap(int[] nums, int k) {
    if (nums == null || nums.length == 0) return nums;
    int n = nums.length, p = 0;
    TreeMap<Integer, Integer> map = new TreeMap<>();
    for (int i = 0; i < k; ++i) map.put(nums[i], i);
    int[] result = new int[n - k + 1];
    result[p++] = map.lastKey();
    for (int i = k; i < n; ++i) {
      if (map.get(nums[i-k]) == i-k) map.remove(nums[i-k]);
      map.put(nums[i], i);
      result[p++] = map.lastKey();
    }
    return result;
  }

  // Time: O(n), Space: O(n)
  public int[] maxNumInSlidingWindowOn(int[] nums, int k) {
    if (nums == null || nums.length == 0) return nums;
    int n = nums.length;
    int[] result = new int[n - k + 1];
    int[] maxFromLeft = new int[n];
    int[] maxFromRight = new int[n];
    maxFromLeft[0] = nums[0];
    maxFromRight[n-1] = nums[n-1];
    for (int i = 1, j = n-2; i < n; ++i, --j) {
      maxFromLeft[i] = i % k == 0 ? nums[i] : Math.max(maxFromLeft[i-1], nums[i]);
      maxFromRight[j] = j % k == k-1 ? nums[j] : Math.max(maxFromRight[j+1], nums[j]);
    }
    for (int i = 0; i <= n-k; ++i) {
      result[i] = Math.max(maxFromRight[i], maxFromLeft[i+k-1]);
    }
    return result;
  }

}