LeetCode-239 Sliding Window Maximum

发布时间：2020-12-14 03:55:27 所属栏目：Windows 来源：网络整理

导读：题目描述 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 positio

题目描述

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,6,7],and k = 3
Output: [3,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;
    }
};

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!