首页 > 代码库 > leetcode 239. Sliding Window Maximum
leetcode 239. Sliding Window Maximum
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.
For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.
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
Therefore, return the max sliding window as [3,3,5,5,6,7].
最原始方法：自己求max
class Solution(object): def maxSlidingWindow(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ maxlist = [] if k == 0: return maxlist if k > 0: length = len(nums)-k+1 for j in range(0,length): max = nums[0+j] for i in range(0+j,k+j): if nums[i] > max: max = nums[i] print max maxlist.append(max) return maxlist
方法一：采取maxlist.append()，改进利用list的max函数求max
class Solution(object): def maxSlidingWindow(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ maxlist = [] if k > 0: length = len(nums)-k+1 for j in range(0,length): eachmax = max(nums[0+j:k+j]) maxlist.append(eachmax) return maxlist if k == 0: return maxlist s = Solution()nums = [1,3,-1,-3,5,3,6,7]k = 3print s.maxSlidingWindow(nums,k)
方法二：再次改进。
class Solution(object): def maxSlidingWindow(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ if not nums: return [] maxlist = [0]*(len(nums)-k+1) if k > 0: length = len(nums)-k+1 for j in range(0,length): eachmax = max(nums[0+j:k+j]) maxlist[j] = eachmax return maxlists = Solution()nums = [1,3,-1,-3,5,3,6,7]k = 3print s.maxSlidingWindow(nums,k)
方法三：时间最短，别人的
class Solution(object): def maxSlidingWindow(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ if not nums: return [] highest = max(nums[:k]) ans = [0]*(len(nums)-k+1) ans[0] = highest last = nums[0] for i in range(1, len(nums)-k+1): if highest == last: highest = max(nums[i:i+k]) elif nums[i+k-1] >= highest: highest = nums[i+k-1] ans[i] = highest last = nums[i] return ans
leetcode 239. Sliding Window Maximum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。