General and Fancy

Given unsorted array, find max value of each subarray of K

• Solution 1: TreeSet for slidng window

      public List<Integer> slidingMax (int[] array, int k) {
          if (array.length < k) {
              return Integer.MIN_VALUE;
          }
          TreeSet<Integer> ts = new TreeSet<>();
          List<Integer> maxArray = new ArrayList<>();
          for(int i = 0; i < array.length - k; i++) {
              if (i < k) {
                  ts.add(array[i]);
              } else {
                 maxArray.add(ts.last());
                 ts.remove(array[i - k]);
                 ts.add(array[i]);
              }
          }
          return maxArray;
      }
  

• Solution 2 : 单调stack.

• Solution 3: DP Based

  这个解法比较惊艳。感觉有一点像merge sort，但是目的不同，所以把combine的过程的结果record了。

  首先考虑，如何分解这个问题？ 如果求every k size smallest

             k
          /     \
        k/2         k/2
       /  \         / \
     k/4   k/4      ....
     ....