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
#include <bits/stdc++.h>
using namespace std;

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

int main() {
	int r = -1;
	cin >> n;

Java

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

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].

C++

Copy
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

Java

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

Python

Copy
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])

C++

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

Java

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

Python

Copy
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()

C++

Copy
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()); }

Java

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

Python

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

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 = []