滑动窗口

滑动窗口，记录左边界，通过map避免字符重复。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0) {
            return 0;
        }

        int l = 0;
        int max = 0;
        Map<Character, Integer> map = new HashMap<>();
        for(int r = 0; r < s.length(); r++) {
            char current = s.charAt(r);
            if(map.containsKey(current)) {
                l = Math.max(l, map.get(current) + 1);
            }
            max = Math.max(r - l + 1, max);
            map.put(current, r);
        }
        return max;
    }
}

该题难点在于如果获取k的滑动窗口内的最大值。维护一个长度为k的单调队列，从大到小排序，当滑动窗口向右移动时，需要比较待加入的值和滑动窗口内最小值。
// 7 2 2 4

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque= new ArrayDeque<>();
        for(int i = 0; i < k; i++) {
            while(!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast();
        }
        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()];
        for(int i = k; i < n; i++) {
            while(!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            while(i - k >= deque.peakFirst()) {
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }
}