滑动窗口，记录左边界，通过map避免字符重复。
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() == 0) {
return 0;
}
int l = 0;
int max = 0;
Map 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 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;
}
}
Original: https://www.cnblogs.com/shitianming/p/16739808.html
Author: 天山琴子
Title: 滑动窗口
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/598664/
转载文章受原作者版权保护。转载请注明原作者出处！