动态规划 滑动窗口最大值

算法的思想是将输入数组分割成有 k 个元素的块。 若 n % k != 0，则最后一块的元素个数可能更少。

开头元素为 i ，结尾元素为 j 的当前滑动窗口可能在一个块内，也可能在两个块中。

情况 1 比较简单。 建立数组 left， 其中 left[j] 是从块的开始到下标 j 最大的元素，方向 左->右。

为了处理更复杂的情况 2，我们需要数组 right，其中 right[j] 是从块的结尾到下标 j 最大的元素，方向 右->左。right 数组和 left 除了方向不同以外基本一致。

两数组一起可以提供两个块内元素的全部信息。考虑从下标 i 到下标 j的滑动窗口。 根据定义，right[i] 是左侧块内的最大元素， left[j] 是右侧块内的最大元素。因此滑动窗口中的最大元素为 max(right[i], left[j])。

算法十分直截了当：从左到右遍历数组，建立数组 left。从右到左遍历数组，建立数组 right。建立输出数组 max(right[i], left[i + k - 1])，其中 i 取值范围为 (0, n - k + 1)。

class Solution {
  public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    if (n * k == 0) return new int[0];
    if (k == 1) return nums;

    int [] left = new int[n];
    left[0] = nums[0];
    int [] right = new int[n];
    right[n - 1] = nums[n - 1];
    for (int i = 1; i < n; i++) {
      // from left to right
      if (i % k == 0) left[i] = nums[i];  // block_start
      else left[i] = Math.max(left[i - 1], nums[i]);

      // from right to left
      int j = n - i - 1;
      if ((j + 1) % k == 0) right[j] = nums[j];  // block_end
      else right[j] = Math.max(right[j + 1], nums[j]);
    }

    int [] output = new int[n - k + 1];
    for (int i = 0; i < n - k + 1; i++)
      output[i] = Math.max(left[i + k - 1], right[i]);

    return output;
  }
}      

if(nums.size() == 0 || k == 0) return vector<int>();
        
        vector<int> result(nums.size()-k+1,0);
        vector<int> left(nums.size(),0);   //从当前元素到块内最左侧元素最大值
        vector<int> right(nums.size(),0);  //从当前元素到块内最右侧元素最大值
        left[0] = nums[0];
        right[nums.size()-1] = nums[nums.size()-1]; 
        for(int i = 1; i < nums.size(); i++){
            //left to right
            if(i%k == 0){
                left[i] = nums[i];
            }else{
                left[i] = max(left[i-1],nums[i]);
            }
           
            //right to left
            int j = nums.size() -1 - i; 
            if((j+1)%k == 0){
                right[j] = nums[j];
            }else{
                right[j] = max(right[j+1],nums[j]);
            }
        }
        
        for(int i = 0; i < result.size(); i++){
            result[i] = max(right[i],left[i+k-1]);
        }
        return result;