[剑指Offer]59-队列的最大值（题目二待补）

题目一：滑动窗口的最大值

题目链接

https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?tpId=13&tqId=11217&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题目描述

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}

思路

总体思路：滑动窗口满足先进先出，可看作队列。因为两端都有pop操作，所以采用双端队列。

原则：

对于新来的元素m，将其与双端队列中的所有元素比较：

- 比m小的x，直接移出队列（因为不再能成为后面滑动窗口的最大值了。）

- 比m大的x，将两者下标差+1与滑动窗口大小比较，判断x是否已不再窗口内，若不在了，则直接移出队列。

经前面的操作，此时队列的第一个元素是滑动窗口的最大值。

由于上面的规则，队列中始终是由大至小的，所以上面两个移出操作分别从双端队列两端至内pop即可，这是采用双端队列的原因

时间复杂度O(n)。PS：暴力方法时间复杂度O(nk),其中k为滑动窗口大小。

其他思路

将滑动窗口看作队列，即是求队列的最大值问题。由于可以用O(1)得到栈的最大值，且可以用两个栈实现一个队列，所以也可以用O(1)的时间得到队列的最大值，故总时间复杂度降到了O(n)。但相比上面的方法，实现更复杂一些。

采用双端队列代码

class Solution {

public:

	vector<int> maxInWindows(const vector<int>& num, unsigned int size)

	{

		vector<int> windowMax;

		deque<int> dq;

		if (num.size() != 0 && size <= num.size()) {

			for (size_t numIndex = 0;numIndex < num.size();++numIndex) {//每个元素

				while (!dq.empty()&&num[dq.back()]<=num[numIndex]) {

					dq.pop_back();

				}

				while (!dq.empty() && numIndex - dq.front() + 1 > size) {

					dq.pop_front();

				}

				dq.push_back(numIndex);

				if (numIndex >= size - 1) {

					windowMax.push_back(num[dq.front()]);

				}

			}

		}

		return windowMax;

	}

};

巴特西