LeetCode-239 Sliding Window Maximum

题目描述

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

题目大意

给定一个数组，以及一个大小为k的窗口，要求将当前位置的窗口内的最大值保存下来，窗口每次向后移动一个位置。

示例

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

解题思路

最简单的方法是，用multiset保存窗口内的数值，由于multiset有序，因此set的最后一个位置保存了set中的最大值，因此每次滑动窗口只需要更新窗口内的数字，将最后一个位置的数值存入结果中即可。

复杂度分析

时间复杂度：O(N^2)

空间复杂度：O(N)

代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size(), fir = 0, sec = 0;
        multiset<int> win;
        vector<int> res;
        if(n == 0)
            return res;
        // 将前k个数字保存到set中
        for(int i = 0; i < k; ++i) {
            win.insert(nums[i]);    
        }
        // 将前k个数字的最大值存入结果中
        res.push_back(*(win.rbegin()));
        // 依次访问之后的数字，更新set，并记录最大值到结果中
        for(int i = k; i < n; ++i) {
            win.erase(win.find(nums[i - k]));
            win.insert(nums[i]);
            res.push_back(*(win.rbegin()));
        }
        
        return res;
    }
};