队列的最大值

• 滑动窗口的最大值
  给定一个数组和滑动窗口的最大值，找出所有滑动窗口里的最大值。例如输入[2, 3, 4, 2, 6, 2, 5, 1]，滑动窗口为 3 ，那么输出 [4, 4, 6, 6, 5]。
  思路一：采用蛮力法，依次扫描每个滑动窗口的最大值。这样如果滑动窗口的大小为 k，数组长度为 n，那么时间复杂度为 O(nk)，对于数据量非常大来说，这似乎不可接受。
  思路二：并不把滑动窗口的每个数值都存入队列，只是将有可能成为最大值的数值存入队列，这用到了双端队列。存入队列的是数值的下标，这样有助于判断数值是否过期，即超过了滑动窗口的大小。

# coding:utf-8
# 借助 collections 里的 deque
from collections import deque
def maxSlideWindow(nums, k):
    if k == 1:
        return nums
    qmax = deque([])
    qmax.append(0)
    res = []

    for x, y in enumerate(nums[1:], 1):
        if nums[qmax[-1]] <= y:
        # 如果数组中当前值大于队列中最后一个值，那么队列中最后一个值不可能成为当前窗口最大值
            for i in range(len(qmax)-1, -1, -1):
                if nums[qmax[i]] > y:
                    break
                else:
                    qmax.pop()
        # 如果数组中当前值小于队列中的值，那么其有可能成为窗口的最大值，将其存入队列
        qmax.append(x)
        #当qmax存在过期数据，即不在移动k范围内的，将其移除出双端队列
        if qmax[0] <= x-k:
            qmax.popleft()
        # 将每次移动窗口的最大值存储到res中
        if x >= k-1:
            res.append(nums[qmax[0]])
    return res

a = [1,2,7,7,8]
print maxSlideWindow(a, 3)

• Minimum Size Subarray Sum
  给定一个整型数组和一个数字s，找到数组中最短的一个连续子数组，使得连续子数组的数字和sum>=s，返回这个最短的连续子数组的长度值

def minSubArrayLen(s, nums):
    """
    :type s: int
    :type nums: List[int]
    :rtype: int
    """
    if not nums:
        return 0
    r = 0
    summ = 0
    minn = None
    l = 0

    while r < len(nums):
        summ += nums[r]
        r += 1
        
        while summ >= s:
            cand = r - l
            summ -= nums[l]
            l += 1
            if minn is None:
                minn = cand
            else:
                minn = min(minn, cand)
    
    if minn is None:
        return 0
    return minn

a = [2, 3, 1, 2, 4, 3]
s = 5
print(minSubArrayLen(s, a))

• Longest Substring Without Repeating Characters
  在一个字符串中寻找没有重复字母的最长子串，返回长度值

def lengthOfLongestSubstring(s):
        """
        :type s: str
        :rtype: int
        """
        used = {}
        max_length = start = 0
        for i, c in enumerate(s):
            if c in used and start <= used[c]:
                start = used[c] + 1
            else:
                max_length = max(max_length, i - start + 1)
            used[c] = i
        return max_length

s = 'abcdabcabcd'
print(lengthOfLongestSubstring(s))