動态規劃 滑動視窗最大值

算法的思想是将輸入數組分割成有 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;