Sliding Window

C++

Copy
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
	multiset<int> s;
	vector<int> ret;
	for(int i = 0; i < k; i++){
		s.insert(nums[i]);
	}
	for(int i = k; i < nums.size(); i++){
		ret.push_back(*s.rbegin());
		s.erase(s.find(nums[i-k]));
		s.insert(nums[i]);
	}
	ret.push_back(*s.rbegin());
	return ret;
}

Java

Copy
static TreeMap<Integer, Integer> multiset = new TreeMap<Integer, Integer>();
static void add(int x) {
	if(multiset.containsKey(x)) {
		multiset.put(x, multiset.get(x) + 1);
	} else {
		multiset.put(x, 1);
	}
}
static void remove(int x) {
	multiset.put(x, multiset.get(x) - 1);

C++

Copy
int n;
set<int> s;
int a[200000], ans;

int main() {
	int r = -1;
	cin >> n; F0R(i,n) cin >> a[i];
	F0R(i,n) {
		while (r < n-1 && !s.count(a[r+1])) s.insert(a[++r]);
		ans = max(ans,r-i+1);
		s.erase(a[i]);
	}
	cout << ans;
}

Java

Copy
public class test{
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int a[] = new int[n];
		for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken());
		int r = -1;
		HashSet<Integer> s = new HashSet<Integer>();
		int ans = 0;

C++

Copy
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
	deque<int> d;
	vector<int> ret;
	for(int i = 0; i < k; i++){
		while(!d.empty() && nums[i] > nums[d.back()]){
			d.pop_back();
		}
		d.push_back(i);
	}
	for(int i = k; i < nums.size(); i++){

Java

Copy
static ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
	ArrayList<Integer> ret = new ArrayList<Integer>();
	ArrayDeque<Integer> d = new ArrayDeque<Integer>();
	for (int i = 0; i < k; i++) {
		while(!d.isEmpty() && nums[i] > nums[d.peekLast()]) {
			d.pollLast();
		}
		d.addLast(i);
	}
	for (int i = k; i < nums.length; i++) {

Python

Copy
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
	d = collections.deque()
	
	def enqueue(i: int) -> None:
		while d and nums[d[-1]] <= nums[i]:
			d.pop()
		d.append(i)
		while d and (i - d[0]) >= k:
			d.popleft()