子串——滑动窗口（八）

LeetCode_239_SlidingWindowMaximum

题目分析：

这题其实和之前题目没有什么关系。放在这，只是因为经典，并且，暂时不知道放其他哪里。
考察的是队列的应用，窗口每次滑动都要删掉一个值，并新增一个值，并取一个最大值。
那么如果构建一个结构，能够高效地增删取最大即可。
维护一个降序队列
查就是队头
增就删队尾更小的
删最有意思，删除的如果是队头就删头，否则不删。
看代码就懂。

解法：

public static int[] maxSlidingWindow(int[] nums, int k) {
    if(nums.length == 0)
        return nums;
    Stack<Integer> vec = new Stack<>();
    int result[] = new int[nums.length - k + 1];

    for (int i = 0; i < k; i++)
        putIn(vec, nums[i]);

    for (int i = k,j = 0; i < nums.length; i++,j++) {
        result[j] = vec.firstElement();
        getOut(vec, nums[j]);
        putIn(vec, nums[i]);
    }
    result[result.length - 1] = vec.firstElement();

    return result;
}

/**
 * T掉小于等于我的 保持队列单调递减
 */
public static void putIn(Stack<Integer> vec, int value){
    while (! vec.empty()) {
        if(vec.lastElement() < value)
            vec.pop();
        else
            break;
    }
    vec.push(value);
}

/**
 * 不是最大的不T
 */
public static void getOut(Stack<Integer> vec, int value){
    if(vec.firstElement() == value)
        vec.removeElementAt(0);
}