Ventana deslizante

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

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);
	if (multiset.get(x) == 0) { multiset.remove(x); }
}
static ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
	ArrayList<Integer> ret = new ArrayList<Integer>();
	for (int i = 0; i < k; i++) { add(nums[i]); }
	for (int i = k; i < nums.length; i++) {
		ret.add(multiset.lastKey());
		remove(nums[i - k]);
		add(nums[i]);
	}
	ret.add(multiset.lastKey());
	return ret;
}

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

#include <bits/stdc++.h>
using namespace std;
 
int n;
set<int> s;
int a[200000], ans;
 
int main() {
	int r = -1;
	cin >> n;
	for (int i = 0; i < n; i++) { cin >> a[i]; }
 
	for (int i = 0; i < n; i++) {
		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;
}

public class Playlist {
	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;
		for (int i = 0; i < n; i++) {
			while (r < n - 1 && !s.contains(a[r + 1])) s.add(a[++r]);
			ans = Math.max(ans, r - i + 1);
			s.remove(a[i]);
		}
		System.out.println(ans);
	}
}

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].
	while nums[right] in unique_songs:
		unique_songs.remove(nums[left])
		left += 1
 
	unique_songs.add(nums[right])
	right += 1
 
	# right - left is the window size.
	ans = max(ans, right - left)
 
print(ans)

vector<int> nums{1, 2, 3, 5, 4};
deque<int> increasing;
deque<int> decreasing;
 
for (int e : nums) {
	while (!increasing.empty() && increasing.back() > e) { increasing.pop_back(); }
	increasing.push_back(e);
}
 
// 1 2 3 4
for (int e : increasing) { cout << e << " "; }
 
for (int e : nums) {
	while (!decreasing.empty() && decreasing.back() < e) { decreasing.pop_back(); }
 
	decreasing.push_back(e);
}
 
// 5 4
for (int e : decreasing) { cout << e << " "; }

int[] nums = {1, 2, 3, 5, 4};
ArrayDeque<Integer> increasing = new ArrayDeque<Integer>();
ArrayDeque<Integer> decreasing = new ArrayDeque<Integer>();
 
for (int e : nums) {
	while (!increasing.isEmpty() && increasing.peekLast() > e) {
		increasing.pollLast();
	}
	increasing.addLast(e);
}
 
System.out.println(increasing);  // [1, 2, 3, 4]
 
for (int e : nums) {
	while (!decreasing.isEmpty() && decreasing.peekLast() < e) {
		decreasing.pollLast();
	}
	decreasing.addLast(e);
}
 
System.out.println(decreasing);  // [5, 4]

nums = [1, 2, 3, 5, 4]
increasing = collections.deque()
decreasing = collections.deque()
 
for e in nums:
	while increasing and increasing[-1] > e:
		increasing.pop()
	increasing.append(e)
 
print(increasing)  # deque([1, 2, 3, 4])
 
for e in nums:
	while decreasing and decreasing[-1] < e:
		decreasing.pop()
	decreasing.append(e)
 
print(decreasing)  # deque([5, 4])

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

public int[] maxSlidingWindow(int[] nums, int k) {
	int[] ret = new int[nums.length - k + 1];
	ArrayDeque<Integer> d = new ArrayDeque<Integer>();
 
	for (int i = 0; i < nums.length; i++) {
		if (!d.isEmpty() && d.peekFirst() <= i - k) { d.pollFirst(); }
 
		while (!d.isEmpty() && nums[d.peekLast()] < nums[i]) { d.pollLast(); }
 
		d.addLast(i);
 
		if (i >= k - 1) { ret[i - k + 1] = nums[d.peekFirst()]; }
	}
 
	return ret;
}

def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
	d = collections.deque()
	ret = []
 
	for i, num in enumerate(nums):
		if d and d[0] <= i - k:
			d.popleft()
 
		while d and nums[d[-1]] < num:
			d.pop()
 
		d.append(i)
 
		if i >= k - 1:
			ret.append(nums[d[0]])
 
	return ret

vector<int> maxSlidingWindow(vector<int> &nums, int k) {
	vector<int> res;
	deque<int> d;
 
	for (int i = 0; i < nums.size(); i++) {
		while (!d.empty() && d.back() < nums[i]) { d.pop_back(); }
 
		d.push_back(nums[i]);
 
		if (i >= k - 1) { res.push_back(d.front()); }
 
		if (i >= k - 1 && !d.empty() && d.front() == nums[i - k + 1]) { d.pop_front(); }
	}
 
	return res;
}

public int[] maxSlidingWindow(int[] nums, int k) {
	int[] ret = new int[nums.length - k + 1];
	ArrayDeque<Integer> d = new ArrayDeque<Integer>();

	for (int i = 0; i < nums.length; i++) {
		while (!d.isEmpty() && d.peekLast() < nums[i]) {
			d.pollLast();
		}

		d.addLast(nums[i]);

		if (i >= k - 1) { ret[i - k + 1] = d.peekFirst(); }

		if (i >= k - 1 && !d.isEmpty() && d.peekFirst() == nums[i - k + 1]) {
			d.pollFirst();
		}
	}

	return ret;
}

def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
	d = collections.deque()
	ret = []
 
	for i, num in enumerate(nums):
		while d and d[-1] < num:
			d.pop()
 
		d.append(num)
 
		if i >= k - 1:
			ret.append(d[0])
 
		if i >= k - 1 and d and d[0] == nums[i - k + 1]:
			d.popleft()
 
	return ret

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.
	 */
	int query() {
		if (s1.empty() && s2.empty()) { return -1e9; }
		if (s1.empty() || s2.empty()) {
			return s1.empty() ? s2.top().second : s1.top().second;
		}
		return max(s1.top().second, s2.top().second);
	}
 
	/**
	 * Add a new element into our MaxQueue. We add the value of this
	 * element itself and the maximum element in the stack s1 after adding.
	 */
	void enqueue(int val) {
		s1.push({val, max(val, (s1.empty() ? val : s1.top().second))});
	}
 
	/**
	 * Remove the first element from our MaxQueue by popping the top
	 * element from s2.
	 */
	void dequeue() {
		if (s2.empty()) {
			// Move all elements from s1 to s2 when s2 is empty
			while (!s1.empty()) {
				int mx = s2.empty() ? s1.top().first : s2.top().second;
				s2.push({s1.top().first, max(mx, s1.top().first)});
				s1.pop();
			}
		}
		s2.pop();
	}
};
 
class Solution {
  public:
	vector<int> maxSlidingWindow(vector<int> &nums, int k) {
		MaxQueue q;
		vector<int> max_vals;
 
		// Fill the queue with elements from the first window
		for (int i = 0; i < k; i++) { q.enqueue(nums[i]); }
		max_vals.push_back(q.query());
 
		/*
		 * We slide the window to the right by removing the first element
		 * from the queue and adding the new element at the end of the queue.
		 * For each window, we add the maximum to our result array max_vals.
		 */
		for (int i = k; i < nums.size(); i++) {
			q.dequeue();
			q.enqueue(nums[i]);
			max_vals.push_back(q.query());
		}
 
		return max_vals;
	}
};

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();
 
		/*
		 * We slide the window to the right by removing the first element
		 * from the queue and adding the new element at the end of the queue.
		 * For each window, we add the maximum to our result array maxVals.
		 */
		for (int i = k; i < n; i++) {
			q.dequeue();
			q.enqueue(nums[i]);
			maxVals[i - k + 1] = q.query();
		}
 
		return maxVals;
	}
 
	private static class MaxQueue {
		/**
		 * For each Pair e, e.a is the value of the element and
		 * e.b is the maximum among all elements in that stack under element e.
		 */
		public Stack<Pair> s1, s2;
 
		public MaxQueue() {
			s1 = new Stack<>();
			s2 = new Stack<>();
		}
 
		/**
		 * Get the maximum element in the MaxQueue.
		 * It is the maximum of both stacks which are stored in s.peek().b.
		 */
		public int query() {
			if (s1.empty() && s2.empty()) { return -1000000000; }
			if (s1.empty() || s2.empty()) {
				return s1.empty() ? s2.peek().b : s1.peek().b;
			}
			return Math.max(s1.peek().b, s2.peek().b);
		}
 
		/**
		 * Add a new element into our MaxQueue. We add the value of this
		 * element itself and the maximum element in the stack s1 after adding.
		 */
		public void enqueue(int val) {
			s1.push(new Pair(val, s1.empty() ? val : Math.max(val, s1.peek().b)));
		}
 
		/**
		 * Remove the first element from our MaxQueue by popping the top
		 * element from s2.
		 */
		public void dequeue() {
			if (s2.empty()) {
				// Move all elements from s1 to s2 when s2 is empty
				while (!s1.empty()) {
					int mx = s2.empty() ? s1.peek().a : s2.peek().b;
					s2.push(new Pair(s1.peek().a, Math.max(mx, s1.peek().a)));
					s1.pop();
				}
			}
			s2.pop();
		}
	}
 
	private static class Pair {
		public int a, b;
 
		public Pair(int a, int b) {
			this.a = a;
			this.b = b;
		}
	}
}

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 = []
 
	def query(self) -> int:
		"""
		Get the maximum element in the MaxQueue.
		It is the maximum of both stacks, stored in the second value of the top of the stack.
		"""
		if not self.s1 and not self.s2:
			return float("-inf")
		if not self.s1 or not self.s2:
			return self.s2[-1][1] if not self.s1 else self.s1[-1][1]
		return max(self.s1[-1][1], self.s2[-1][1])
 
	"""
    	Add a new element into the MaxQueue. We add the value of this
    	element and the maximum element in stack s1 after adding.
    	"""
 
	def enqueue(self, val: int):
		max_val = max(val, self.s1[-1][1]) if self.s1 else val
		self.s1.append((val, max_val))
 
	"""
    	Remove the first element from our MaxQueue by popping the top
    	element from s2.
    	"""
 
	def dequeue(self):
		# Move all elements from s1 to s2 when s2 is empty
		if not self.s2:
			while self.s1:
				val = self.s1.pop()[0]
				max_val = max(val, self.s2[-1][1]) if self.s2 else val
				self.s2.append((val, max_val))
		self.s2.pop()
 
 
class Solution:
	def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
		q = MaxQueue()
		max_vals = []
 
		# Fill the queue with elements from the first window
		for i in range(k):
			q.enqueue(nums[i])
		max_vals.append(q.query())
 
		"""
		We slide the window to the right by removing the first element
		from the queue and adding the new element at the end of the queue.
		For each window, we add the maximum to our result array max_vals.
		"""
		for i in range(k, len(nums)):
			q.dequeue()
			q.enqueue(nums[i])
			max_vals.append(q.query())
 
		return max_vals