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);

Python

Copy
from sortedcontainers import SortedList


class Solution:
	def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
		s = SortedList(nums[:k])
		ret = []

		for i in range(k, len(nums)):
			ret.append(s[-1])
			s.remove(nums[i - k])
			s.add(nums[i])

		ret.append(s[-1])
		return ret

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;
}

Python

Copy
n = int(input().strip())
nums = [int(v) for v in input().split(" ")]

ans = -float("inf")
left, right = 0, 0
unique_songs = set()

while right < n:
	# Notice that all the songs in unique_songs are unique in each iteration.
	# We keep this property by shrinking the window before inserting nums[right].

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++) {
		ret.push_back(nums[d.front()]);
		if (!d.empty() && d.front() <= i - k) { d.pop_front(); }

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++) {
		ret.add(nums[d.peekFirst()]);
		if (!d.isEmpty() && d.peekFirst() <= i - k) { d.pollFirst(); }

Python

Copy
from typing import List


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)

C++

Copy
struct MaxQueue {
	/**
	 * For each pair<int, int> e, e.first is the value of the element and
	 * e.second is the maximum among all elements in that stack under element e.
	 */
	stack<pair<int, int>> s1, s2;

	/**
	 * Get the maximum element in the MaxQueue.
	 * It is the maximum of both stacks which are stored in s.top().second.

Java

Copy
class Solution {
	public int[] maxSlidingWindow(int[] nums, int k) {
		MaxQueue q = new MaxQueue();
		int n = nums.length;
		int[] maxVals = new int[n - k + 1];

		// Fill the queue with elements from the first window
		for (int i = 0; i < k; i++) { q.enqueue(nums[i]); }
		maxVals[0] = q.query();

Python

Copy
class MaxQueue:
	def __init__(self):
		"""
		For each pair (val, max_val) in the stacks:
		- val: The value of the element.
		- max_val: The maximum among all elements in that stack under element val.
		"""
		self.s1 = []
		self.s2 = []